本文共 1251 字，大约阅读时间需要 4 分钟。
题意：询问一个字符串每个前缀有多少不同的子串
做了一下SDOI2016R1D2，题好水啊随便AK
强行开map上SAM
#include #include #include #include #include #include using namespace std;typedef long long ll;#define fir first#define sec secondconst int N=3e5+5, P=1e9+7;inline int read() { char c=getchar(); int x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int n, s[N]; ll ans;struct meow { map ch; int par, val;}t[N];int sz=1, root=1, last=1;void extend(int c) { int p=last, np=++sz; t[np].val = t[p].val+1; for(; p && !t[p].ch[c]; p=t[p].par) t[p].ch[c]=np; if(!p) t[np].par = root; else { int q=t[p].ch[c]; if(t[q].val == t[p].val+1) t[np].par=q; else { ans -= t[q].val - t[p].val; int nq=++sz; t[nq]=t[q]; t[nq].val = t[p].val+1; t[q].par = t[np].par = nq; ans += t[q].val - t[nq].val; ans ++; for(; p && t[p].ch[c]==q; p=t[p].par) t[p].ch[c] = nq; } } ans+=t[np].val - t[t[np].par].val; last=np;}int main() { //freopen("in","r",stdin); freopen("incantation.in","r",stdin); freopen("incantation.out","w",stdout); n=read(); for(int i=1; i<=n; i++) { s[i]=read(); extend(s[i]); printf("%lld\n",ans); }}
转载地址：http://wxema.baihongyu.com/