首页 > 代码库 > 【后缀自动机】SPOJ 8222-最多重复子串
【后缀自动机】SPOJ 8222-最多重复子串
题意:
一个长度不超过250000的字符串,求出它长度为i的子串最多出现了多少次。
后缀自动机练习题...虽说是用Cube评测的不过时限仍然鬼畜。
考虑SAM的性质:
一个串的SAM肯定可以接受这个串的所有子串。SAM上的每一个点代表了一个子串。
主链:SAM上最长的那条链,也就是说从根走到主链的尾端就是整个字符串。
用t[i]记录i号点表示的子串的出现次数,沿着主链走一遍,很明显,主链上所有的点都代表了一个前缀,每个前缀都出现过。因此主链上的点的t初始值为1。
接着,之前提到过,一个点的pre上的点和它,这些点表示的子串,具有相同的后缀。
既然i出现过,那么i.pre肯定出现过。因此对一个点+1就代表对整条pre链+1。
最后,因为step[i]表示i的长度,因此对于所有的step[i]取一个最大值,记录到ans中就可以了。
这次换了个SAM的写法,把之前的for循环改成了while,结果忘记了一个迭代步骤,调了统计过程很久才发现原来是SAM构错了...
一开始写的是t[i]+1之后,沿着pre链,将i的pre上的所有点都+1,结果TLE了。参考了一下沐阳神犇的代码,发现只要统计前缀和就行了...
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #define maxn 255000*2 6 using namespace std; 7 8 struct node { int s[26],num,pre; } Suf[maxn]; 9 int step[maxn],ans[maxn],t[maxn],f[maxn];10 int i,j,n,m,k,cnt = 1,last = 1,root = 1,len;11 char S[maxn];12 13 void add(int nxt)14 {15 int now = ++cnt, p = last;16 step[now] = step[p] + 1;17 while ( p && !Suf[p].s[nxt] ) Suf[p].s[nxt] = now, p = Suf[p].pre;18 if (!p) Suf[now].pre = root;19 else20 {21 int q = Suf[p].s[nxt];22 if (step[q] == step[p] + 1) Suf[now].pre = q;23 else24 {25 int nq = ++cnt;26 step[nq] = step[p] + 1;27 Suf[nq] = Suf[q];28 Suf[q].pre = Suf[now].pre = nq;29 while ( p && Suf[p].s[nxt] == q ) Suf[p].s[nxt] = nq,p = Suf[p].pre;30 }31 }32 last = now;33 }34 35 bool cmp(int a,int b) { return step[a] < step[b]; }36 37 int main()38 {39 len = strlen(S+1);40 41 for (i = 1; i <= len; i++) add(S[i]-‘a‘); 42 43 for (i = 1; i <= cnt; i++) f[i] = i;44 stable_sort(f+1,f+1+cnt,cmp);45 46 int now = root;47 for (i = 1; i <= len; i++)48 {49 now = Suf[now].s[S[i]-‘a‘];50 t[now]++;51 }52 53 for (i = cnt; i > 1; i--)54 {55 ans[step[f[i]]] = max(ans[step[f[i]]],t[f[i]]);56 if (Suf[f[i]].pre > 1) t[Suf[f[i]].pre] += t[f[i]];57 }58 59 for (i = 1; i <= len; i++)60 printf("%d\n",ans[i]);61 62 return 0;63 }
【后缀自动机】SPOJ 8222-最多重复子串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。