【poj1509】Glass Beads

2015.06.16 10:52 Tue | 12次阅读 | 旧日oi | 固定链接 | 源码

求一个字符串从哪一位开始扫字典序最小
算法1:最小表示法,模板题

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
char s[10005];
int T,len;
int work()
{
    int i=0,j=1,k=0,t;
    while(i<len&&j<len&&k<len)
    {
        t=s[(i+k)%len]-s[(j+k)%len];
        if(!t) k++;
        else
        {
            if(t>0) i+=k+1;
            else j+=k+1;
            if(i==j) i++;
            k=0;
        }
    }
    return min(i,j);
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%s",s);len=strlen(s);
        printf("%d\n",work()+1);
    }
}
算法2:后缀自动机
算法理解进度:20%
把字符串复制一遍加到自动机中。然后采用贪心的策略遍历,以helloworld举例,把串变成helloworldhelloword,已知答案为dhelloworl,那么在自动机中的顺序就应该是lrowollehd,建成自动机后,从根节点找出trans(根节点,i)=0的最小的i,那么这个i一定是最小表示的第一个字符,在利在例子中也就是d这个字母,然后就这么找len次就可以了,最后找出l的位置,这个位置肯定是在复制一遍后的串中的,所以直接-len+1就行。
具体的细节或者正确性不要问我,我也就是这么理解个大概……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int T,len;
struct SAM
{
    struct node
    {
        int son[26],len,fa;
    }a[20005];
    int last,tot;
    void init()
    {
        memset(a,0,sizeof(a));
        last=tot=1;
    }
    void insert(int x)
    {
        int p=last,np=++tot;last=np;
        a[np].len=a[p].len+1;
        for(;!a[p].son[x]&&p;p=a[p].fa) a[p].son[x]=np;
        if(!p) a[np].fa=1;
        else
        {
            int q=a[p].son[x];
            if(a[q].len==a[p].len+1) a[np].fa=q;
            else
            {
                int nq=++tot;a[nq]=a[q];
                a[nq].len=a[p].len+1;a[q].fa=a[np].fa=nq;
                for(;a[p].son[x]==q;p=a[p].fa) a[p].son[x]=nq;
            }
        }
    }
    void solve()
    {
        int p=1;
        for(int i=1;i<=len;i++)
        {
            for(int j=0;j<26;j++)
            if(a[p].son[j])
            {
                p=a[p].son[j];
                break;
            }
        }
        printf("%d\n",a[p].len-len+1);
    }
}sam;
char s[10005];
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%s",s);len=strlen(s);
        sam.init();
        for(int i=0;i<2*len;i++) sam.insert(s[i%len]-'a');
        sam.solve();
    }
}```