poj 1509 字符串的最小表示法 （SAM 后缀自动机）

http://poj.org/problem?id=1509

题意：就是求一个字符串的最小表示法开头字符的位置，如果有多个，求最小的位置。

思路：这道题用后缀自动机来做本身就是闲着，有点大材小用的感觉，这道题有别的更加精简的算法的，时间复杂度也为O(n)，但是这里用SAM做能对SAM有更加清晰的认识，纯粹是为了练习SAM吧。

将原字符S串复制一下加到原字符串之后变成SS，则我们便是要求SS长度为|S|的字典序最小的字串，于是我们可以构造出SS的SAM，从root开始每次走最小编号的转移，走了|S|步以后到达的状态即为我们要求的子串（设为p），因为我们是要求开头的位置，并且是最小的一个，所以我们在每一个状态里保存一个变量l，表示这个状态在SS中出现的最左边的位置，则答案即为p->l-|s|+1，下面是代码。

#include <iostream>#include <string.h>#include <stdio.h>#include <algorithm>#define maxn 40010using namespace std;char str[maxn>>1];struct sam{    sam *go[26],*par;    int val;    int l,po;}*root,*tail,que[maxn],*top[maxn];int tot;void add(int c,int l,int po){    sam *p=tail,*np=&que[tot++];    np->po=po;    np->val=l;    while(p&&p->go[c]==NULL)    p->go[c]=np,p=p->par;    if(p==NULL) np->par=root;    else    {        sam *q=p->go[c];        if(p->val+1==q->val) np->par=q;        else        {            sam *nq=&que[tot++];            *nq=*q;            nq->val=p->val+1;            np->par=q->par=nq;            while(p&&p->go[c]==q) p->go[c]=nq,p=p->par;        }    }    tail=np;}int c[maxn],len;void init(){    memset(que,0,sizeof(que));    tot=0;    len=1;    root=tail=&que[tot++];}void solve(int n){    memset(c,0,sizeof(c));    int i;    for(i=0;i<tot;i++)    c[que[i].val]++;    for(i=1;i<len;i++)    c[i]+=c[i-1];    for(i=0;i<tot;i++)    top[--c[que[i].val]]=&que[i];    for(sam *p=root;;p=p->go[str[p->val+1]-'a'])    {        p->l=p->po;        //printf("%c",str[p->val+1]);        if (p->val==len-1)break;    }    sam *p;    for(i=tot-1;i>=0;i--)    {        p=top[i];        if(p->par)        {            sam *q=p->par;            if(q->l==0||q->l>p->l)            q->l=p->l;        }    }    p=root;    int tmp=n;    while(tmp--)    {        int i;        for(i=0;i<26;i++)        {            if(p->go[i])            {                p=p->go[i];                break;            }        }    }    int ans=p->l-n+1;    printf("%d\n",ans);}int main(){    //freopen("dd.txt","r",stdin);    int ncase;    scanf("%d",&ncase);    while(ncase--)    {        scanf("%s",str+1);        init();        int l=strlen(str+1),i;        for(i=1;i<=l;i++)        {            str[i+l]=str[i];        }        for(i=1;i<=2*l;i++)        add(str[i]-'a',len++,i);        solve(l);    }    return 0;}

这里再放一个专门求字符串最小表示的算法的代码。简单有效。。。

#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 100000int min(int a,int b){    return a<b?a:b;}int min_Str(char *str){    int i,j,k,len=strlen(str);    i=0,j=1;    memcpy(str+len,str,len);    while(j<len&&i<len)    {        k=0;        while(str[i+k]==str[j+k])        k++;        if(k>=len)        break;        if(str[i+k]>str[j+k])        i=i+k+1;        else        j=j+k+1;        if(i==j)        j++;    }    return min(i,j);}char str[MAXN];int main(){   //freopen("dd.txt","r",stdin);    int ncase;    scanf("%d",&ncase);    while(ncase--)    {   memset(str,'\0',sizeof(str));        scanf("%s",str);        printf("%d\n",1+min_Str(str));    }    return 0;}