【POJ1509】Glass Beads 【后缀自动机】

题意

  给出一个字符串，求它的最小表示法。

分析

这个题当然可以用最小表示法做啦！但是我是为了学后缀自动机鸭！

我们把这个字符串长度乘二，然后建SAM，然后在SAM上每次跑最小的那个字母，找出长度为n的时候就停下。如果停下的那个状态时u，那么ans=st[u].len-n+1

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <map>

using namespace std;
const int maxn=20000+100;
char s[maxn];
int n,T;
struct state{
    map<char,int>next;
    int len,link;
}st[4*maxn];
int last,cnt,cur;
void init(){
    last=cur=0;
    cnt=1;
    st[0].len=0;
    st[0].link=-1;
    st[0].next.clear();
}
void build(char c){
    cur=cnt++;
    st[cur].next.clear();
    st[cur].len=st[last].len+1;
    int p;
    for(p=last;p!=-1&&!st[p].next.count(c);p=st[p].link)
        st[p].next[c]=cur;
    if(p==-1)
        st[cur].link=0;
    else{
        int q=st[p].next[c];
        if(st[p].len+1==st[q].len)
            st[cur].link=q;
        else{
            int clone=cnt++;
            st[clone].next=st[q].next;
            st[clone].link=st[q].link;
            st[clone].len=st[p].len+1;
            for(;p!=-1&&st  [p].next[c]==q;p=st[p].link)
                st[p].next[c]=clone;
            st[q].link=clone;st[cur].link=clone;
        }
    }
    last=cur;
}
int main(){
    scanf("%d",&T);
    for(int t=1;t<=T;t++){
        scanf("%s",s);
        n=strlen(s);
        for(int i=0;i<n;i++)
            s[i+n]=s[i];
        init();
        for(int i=0;i<n;i++)
            build(s[i]);
        for(int i=n;i<2*n;i++)
            build(s[i]);
        int u=0;
        for(int i=0;i<n;i++){
            for(int j='a';j<='z';j++){
                if(st[u].next.count(j)){
                    u=st[u].next[j];
                    break;
                }
            }
        }
        int ans=st[u].len-n+1;
        printf("%d\n",ans);
    }
return 0;
}