专门做环保设备的网站,seo企业网站优化,网站备案申请流程,免费做印章的网站题目链接: https://codeforces.com/contest/235/problem/C 题解: 对大串建后缀自动机 对询问串复制拆环。这里一定要注意是复制一个循环节不是复制整个串#xff01;循环节是要整除的那种 然后要做的实际上是在大串上跑#xff0c;每经过一个点求出当前的最长公共子串#x…题目链接: https://codeforces.com/contest/235/problem/C 题解: 对大串建后缀自动机 对询问串复制拆环。这里一定要注意是复制一个循环节不是复制整个串循环节是要整除的那种 然后要做的实际上是在大串上跑每经过一个点求出当前的最长公共子串如果大于等于\(n\)的话则向上跳Parent树找到\(n\in [minlen[v],maxlen[v]]\)的那个祖先\(v\) 这玩意直接做复杂度是错的(虽然貌似网上有直接做过了的)但是我们可以递推 考虑递推实际上就是维护一个长度为\(m\)(询问串长度)的队列每次删掉第一个字符(就是判断如果当前最长公共子串长\(n\)就变成\(n-1\), 如果需要的话跳到父亲)然后每次长度达到\(n\)时\(anslen[u]\)即可。 代码 #includecstdio
#includecstdlib
#includecstring
using namespace std;const int N 1e6;
const int S 26;
char a[N3];
char b[(N1)3];
int son[(N1)3][S3];
int fa[(N1)3];
int len[(N1)3];
int vis[(N1)3];
int ord[(N1)3];
int buc[N3];
int nxt[N3];
int sz[(N1)3];
int n,q,m,siz,rtn,lstpos;void initSAM()
{siz rtn lstpos 1;
}void KMP()
{nxt[0] nxt[1] 0;for(int i2; im; 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; pfa[p]) {son[p][ch] np;}if(p0) {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; pfa[p]) {son[p][ch] nq;}}}
}int main()
{initSAM();scanf(%s,a1); n strlen(a1);for(int i1; in; i) a[i]-96;for(int i1; in; i) {insertchar(a[i]);}for(int i1; isiz; i) buc[len[i]];for(int i1; in; i) buc[i] buc[i-1];for(int isiz; i1; i--) ord[buc[len[i]]--] i;for(int isiz; i1; i--){int u ord[i];sz[fa[u]] sz[u];}scanf(%d,q);while(q--){scanf(%s,b1); m strlen(b1);for(int i1; im; i) b[i]-96;KMP();int cyclen nxt[m];while(cyclen0 m%(m-cyclen)!0){cyclen nxt[cyclen];}cyclen m-cyclen;for(int i1; icyclen; i) b[im] b[i];int u rtn,cur 0,ans 0;for(int i1; imcyclen; 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(curm){ans sz[u];cur--;if(curlen[fa[u]]){u fa[u];}}}printf(%d\n,ans);}return 0;
} 转载于:https://www.cnblogs.com/suncongbo/p/11070462.html
