Spoj REPEATS 后缀自动机+set

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)

 #include<cstdio>

 #include<cstring>

 #include<set>

 const int len(),INF();

 struct SamNode{int nx[],pre,step;}sam[len*+];

 std::set<int>RBT[len*+];int size[len*+],rt[len*+];

 std::set<int>::iterator ii,ti;

 int top=,root=,now=,last,lastson;

 int cnt[len+],p[len*+],mn[len*+];

 void insert(int x)

 {

     last=now;now=++top;

     sam[now].step=sam[last].step+;

     size[now]=;mn[now]=INF;rt[now]=now;

     RBT[now].insert(sam[now].step);

     for(;!sam[last].nx[x]&&last;last=sam[last].pre)

         sam[last].nx[x]=now;

     if(!last)sam[now].pre=root;

     else

     {

         lastson=sam[last].nx[x];

         if(sam[lastson].step==sam[last].step+)sam[now].pre=lastson;

         else

         {

             sam[++top]=sam[lastson];

             sam[top].step=sam[last].step+;

             mn[top]=INF;rt[top]=top;size[top]=;

             sam[now].pre=sam[lastson].pre=top;

             for(;sam[last].nx[x]==lastson&&last;last=sam[last].pre)

                 sam[last].nx[x]=top;

         }

     }

 }

 int T,n,ans;char ch[];

 void swap(int &a,int &b){if(a==b)return;a^=b;b^=a;a^=b;}

 int min(int a,int b){return a>b?b:a;}

 int max(int a,int b){return a<b?b:a;}

 void union_set(int x,int y)

 {

     if(size[rt[x]]<size[rt[y]])swap(rt[x],rt[y]);

     int val;

     for(ii=RBT[rt[y]].begin();ii!=RBT[rt[y]].end();ii++)

     {

         val=*(ii);

         RBT[rt[x]].insert(val);

         ti=RBT[rt[x]].find(val);

         if(ti!=RBT[rt[x]].begin())

         {

             ti--;mn[rt[x]]=min(mn[rt[x]],val-*(ti));ti++;

         }

         if(ti!=RBT[rt[x]].end())

         {

             ti++;

             if(ti!=RBT[rt[x]].end())mn[rt[x]]=min(mn[rt[x]],*(ti)-val);

         }

         size[rt[x]]++;

     }

     RBT[rt[y]].clear();

 }

 void total()

 {

     for(int i=;i<=n;i++)cnt[i]=;

     for(int i=;i<=top;i++)cnt[sam[i].step]++;

     for(int i=;i<=n;i++)cnt[i]+=cnt[i-];

     for(int i=top;i>=;i--)p[cnt[sam[i].step]--]=i;

     for(int i=top;i>=;i--)

     {

         ans=max(ans,(sam[p[i]].step+mn[rt[p[i]]])/mn[rt[p[i]]]);

         union_set(sam[p[i]].pre,p[i]);

     }

     RBT[rt[]].clear();

 }

 int main()

 {

     scanf("%d",&T);

     while(T--)

     {

         memset(sam,,sizeof(sam));

         top=,root=,now=;ans=;

         mn[]=INF;rt[]=;size[]=;

         scanf("%d",&n);

         for(int i=;i<=n;i++)

         {

             scanf("%s",ch);

             insert(ch[]-'a');

         }

         total();

         printf("%d\n",ans);

     }

     return ;

 }