題目鏈接: https://codeforces.com/contest/235/problem/C
題解:
對大串建后綴自動機
對詢問串復制拆環。這里一定要注意是復制一個循環節不是復制整個串！循環節是要整除的那種
然后要做的實際上是在大串上跑，每經過一個點求出當前的最長公共子串，如果大于等于\(n\)的話，則向上跳Parent樹找到\(n\in [minlen[v],maxlen[v]]\)的那個祖先\(v\)
這玩意直接做復雜度是錯的(雖然貌似網上有直接做過了的)，但是我們可以遞推！
考慮遞推，實際上就是維護一個長度為\(m\)(詢問串長度)的隊列，每次刪掉第一個字符(就是判斷如果當前最長公共子串長\(=n\)就變成\(n-1\), 如果需要的話跳到父親)，然后每次長度達到\(n\)時\(ans+=len[u]\)即可。
代碼
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;const int N = 1e6;
const int S = 26;
char a[N+3];
char b[(N<<1)+3];
int son[(N<<1)+3][S+3];
int fa[(N<<1)+3];
int len[(N<<1)+3];
int vis[(N<<1)+3];
int ord[(N<<1)+3];
int buc[N+3];
int nxt[N+3];
int sz[(N<<1)+3];
int n,q,m,siz,rtn,lstpos;void initSAM()
{siz = rtn = lstpos = 1;
}void KMP()
{nxt[0] = nxt[1] = 0;for(int i=2; i<=m; i++){nxt[i] = nxt[i-1];while(nxt[i] && b[nxt[i]+1]!=b[i]){nxt[i] = nxt[nxt[i]];}if(b[nxt[i]+1]==b[i]) nxt[i]++;}
}void insertchar(char ch)
{int p = lstpos,np; siz++; np = lstpos = siz; len[np] = len[p]+1; sz[np]++;for(; p && son[p][ch]==0; p=fa[p]) {son[p][ch] = np;}if(p==0) {fa[np] = rtn;}else{int q = son[p][ch];if(len[q]==len[p]+1) {fa[np] = q;}else{siz++; int nq = siz; len[nq] = len[p]+1;memcpy(son[nq],son[q],sizeof(son[q]));fa[nq] = fa[q]; fa[q] = fa[np] = nq;for(; p && son[p][ch]==q; p=fa[p]) {son[p][ch] = nq;}}}
}int main()
{initSAM();scanf("%s",a+1); n = strlen(a+1);for(int i=1; i<=n; i++) a[i]-=96;for(int i=1; i<=n; i++) {insertchar(a[i]);}for(int i=1; i<=siz; i++) buc[len[i]]++;for(int i=1; i<=n; i++) buc[i] += buc[i-1];for(int i=siz; i>=1; i--) ord[buc[len[i]]--] = i;for(int i=siz; i>=1; i--){int u = ord[i];sz[fa[u]] += sz[u];}scanf("%d",&q);while(q--){scanf("%s",b+1); m = strlen(b+1);for(int i=1; i<=m; i++) b[i]-=96;KMP();int cyclen = nxt[m];while(cyclen>0 && m%(m-cyclen)!=0){cyclen = nxt[cyclen];}cyclen = m-cyclen;for(int i=1; i<cyclen; i++) b[i+m] = b[i];int u = rtn,cur = 0,ans = 0;for(int i=1; i<m+cyclen; i++){while(u && son[u][b[i]]==0) {u = fa[u]; cur = len[u];}if(son[u][b[i]]!=0) {u = son[u][b[i]]; cur++;}else {u = rtn; cur = 0;}if(cur==m){ans += sz[u];cur--;if(cur<=len[fa[u]]){u = fa[u];}}}printf("%d\n",ans);}return 0;
}
