BZOJ 2882 工艺 （字符串最小循环同构）

题目大意：

给一个长度小于等于30W的数列，求其最小循环同构。

算法讨论：

在自动机长倍长走S后即可。注意这里面是数字，要用map存储。 今天才知道要开四倍长。

Codes：

 #include <bits/stdc++.h>

 using namespace std;

 const int L =  + ;

 int n, a[L<<], ans;

 struct State{

   int len, pre;

   map <int, int> next;

   State(){

     len = pre = ;

     next.clear();

   }

   void clear(){

     len = pre = ;

     next.clear();

   }

 }st[L<<];

 struct SuffixAutomaton{

   int sz, last;

   void Init(){

     last = sz = ;

     st[].len = ; st[].pre = -;

     sz ++;

   }

   void Extend(int c){

     int cur = sz ++;

     st[cur].len = st[last].len + ;

     int p;

     for(p = last; p != - && !st[p].next[c]; p = st[p].pre)

       st[p].next[c] = cur;

     if(p == -) st[cur].pre = ;

     else{

       int q = st[p].next[c];

       if(st[q].len == st[p].len + ) st[cur].pre = q;

       else{

         int cle = sz ++;

         st[cle].len = st[p].len + ;

         st[cle].pre = st[q].pre;

         st[cle].next = st[q].next;

         for(; p != - && st[p].next[c] == q; p = st[p].pre)

           st[p].next[c] = cle;

         st[q].pre = st[cur].pre = cle;

       }

     }

     last = cur;

   }

 }SAM;

 void Input(){

   scanf("%d", &n);

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

     scanf("%d", &a[i]);

 }

 void Output(){

   bool flag = false;

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

     if(!flag){

       flag = true;

       printf("%d", a[i % n]);

     }

     else

       printf(" %d", a[i % n]);

   }

   printf("\n");

 }

 void Solve(){

   SAM.Init();

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

     a[i + n] = a[i];

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

     SAM.Extend(a[i]);

   int p = ;

   map <int, int>:: iterator pos;

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

     for(pos = st[p].next.begin(); pos != st[p].next.end(); ++ pos){

       p = (*pos).second;

       break;

     }

   }

   ans = st[p].len - n;

 }

 int main(){

   Input();

   Solve();

   Output();

   return ;

 }

BZOJ 2882