Spoj REPEATS 后缀自动机+setREPEATS - Repeats

93 阅读 0 评论 62 点赞

我是靠谱客的博主受伤小丸子，最近开发中收集的这篇文章主要介绍Spoj REPEATS 后缀自动机+setREPEATS - Repeats，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

REPEATS - Repeats

链接：http://www.spoj.com/problems/REPEATS

题意：求S串中某个子串连续循环次数最多的次数。

想法：

从暴力开始，枚举所有串，求出这些串的最小循环节长度，算出连续循环次数。

如何求一个串S的最小循环节长度：即next表示这个串最长后缀与前缀相等的长度，最小循环节长度=S.length-next。

KMP可以解决next，于是O(n^2)暴力求出答案。然后优化一下。

上图ans=(len+(x-y))/(x-y)。

在SAM一个节点上，以其{right}为右端点长度为[min,max]的串都相等。那么对应上图，{right}中距离最小的两个点x,y.ans=(max+|x-y|)/|x-y|。

用平衡树维护{right}，再启发式合并。

总O(nlog^2n)

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<set>
 4 const int len(50000),INF(200000);
 5 struct SamNode{int nx[2],pre,step;}sam[len*2+10];
 6 std::set<int>RBT[len*2+10];int size[len*2+10],rt[len*2+10];
 7 std::set<int>::iterator ii,ti;
 8 int top=1,root=1,now=1,last,lastson;
 9 int cnt[len+10],p[len*2+10],mn[len*2+10];
10 void insert(int x)
11 {
12     last=now;now=++top;
13     sam[now].step=sam[last].step+1;
14     size[now]=1;mn[now]=INF;rt[now]=now;
15     RBT[now].insert(sam[now].step);
16     for(;!sam[last].nx[x]&&last;last=sam[last].pre)
17         sam[last].nx[x]=now;
18     if(!last)sam[now].pre=root;
19     else
20     {
21         lastson=sam[last].nx[x];
22         if(sam[lastson].step==sam[last].step+1)sam[now].pre=lastson;
23         else
24         {
25             sam[++top]=sam[lastson];
26             sam[top].step=sam[last].step+1;
27             mn[top]=INF;rt[top]=top;size[top]=0;
28             sam[now].pre=sam[lastson].pre=top;
29             for(;sam[last].nx[x]==lastson&&last;last=sam[last].pre)
30                 sam[last].nx[x]=top;
31         }
32     }
33 }
34 int T,n,ans;char ch[1];
35 void swap(int &a,int &b){if(a==b)return;a^=b;b^=a;a^=b;}
36 int min(int a,int b){return a>b?b:a;}
37 int max(int a,int b){return a<b?b:a;}
38 void union_set(int x,int y)
39 {
40     if(size[rt[x]]<size[rt[y]])swap(rt[x],rt[y]);
41     int val;
42     for(ii=RBT[rt[y]].begin();ii!=RBT[rt[y]].end();ii++)
43     {
44         val=*(ii);
45         RBT[rt[x]].insert(val);
46         ti=RBT[rt[x]].find(val);
47         if(ti!=RBT[rt[x]].begin())
48         {
49             ti--;mn[rt[x]]=min(mn[rt[x]],val-*(ti));ti++;
50         }
51         if(ti!=RBT[rt[x]].end())
52         {
53             ti++;
54             if(ti!=RBT[rt[x]].end())mn[rt[x]]=min(mn[rt[x]],*(ti)-val);
55         }
56         size[rt[x]]++;
57     }
58     RBT[rt[y]].clear();
59 }
60 void total()
61 {
62     for(int i=1;i<=n;i++)cnt[i]=0;
63     for(int i=1;i<=top;i++)cnt[sam[i].step]++;
64     for(int i=1;i<=n;i++)cnt[i]+=cnt[i-1];
65     for(int i=top;i>=1;i--)p[cnt[sam[i].step]--]=i;
66     for(int i=top;i>=2;i--)
67     {
68         ans=max(ans,(sam[p[i]].step+mn[rt[p[i]]])/mn[rt[p[i]]]);
69         union_set(sam[p[i]].pre,p[i]);
70     }
71     RBT[rt[1]].clear();
72 }
73 int main()
74 {
75     scanf("%d",&T);
76     while(T--)
77     {
78         memset(sam,0,sizeof(sam));
79         top=1,root=1,now=1;ans=0;
80         mn[1]=INF;rt[1]=1;size[1]=0;
81         scanf("%d",&n);
82         for(int i=1;i<=n;i++)
83         {
84             scanf("%s",ch);
85             insert(ch[0]-'a');
86         }
87         total();
88         printf("%dn",ans);
89     }
90     return 0;
91 }