回文自动机小结

2016.02.19 20:10 Fri | 54次阅读 | 旧日oi | 固定链接 | 源码

URAL2040

题目大意

给出一个空串,每次添加一个字符,如果添加后产生了新的回文串,输出1,否则输出0.
n<=5000000

题解

回文自动机。
用途:识别一个串的所有回文串。
结构:len表示节点代表的回文串的长度,fail指向这个回文串的最长后缀回文串,son[x]表示这个回文串两边各添加一个字符x对应的节点
构造方法:增量构造法,假设已经构造好了串s的回文自动机,设以最后一个字符为结尾的回文串在节点last,新加入一个字符x,s[++n]=x,如果s[n-len[last]-1]!=s[n],那么last就要沿着fail指针走,直到s[n-len[last]-1]==s[n],为了保证一定能找到,开始要建立一个长度为-1的节点。找到一个last满足条件后,如果son[last][x]为空,说明新产生了一个回文串,建立新节点,
len[++tot]=len[last]+2.
然后处理fail,考虑last的fail指针,同样的,如果s[n-len[fail[last]]-1]!=s[n],就也得向上走,直到找到。fail[tot]=son[find(fail[last])][x];
这样就构建好了。
时空复杂度:每个串最多新建一个节点,所以空间O(n),时间上,由于len总共加了2*n,fail每次向上走至少走了2,所以还是O(n)。

模板&&我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 5000005
char s[N];
struct PAM
{
    int son[N][2],fail[N],last,tot,n,len[N];
    short s[N];
    void init()
    {
        memset(son[0],0,sizeof(son[0]));
        memset(son[1],0,sizeof(son[1]));
        tot=1;last=0,n=0;
        fail[0]=fail[1]=1;
        len[0]=0;len[1]=-1;
        s[0]=-1;
    }
    int find(int x)
    {
        while(s[n-len[x]-1]!=s[n]) x=fail[x];
        return x;
    }
    int insert(int x)
    {
        s[++n]=x;
        int now=find(last);
        if(!son[now][x])
        {
            len[++tot]=len[now]+2;
            memset(son[tot],0,sizeof(son[tot]));
            fail[tot]=son[find(fail[now])][x];
            last=son[now][x]=tot;
            return 1;
        }
        last=son[now][x];
        return 0;
    }
}pam;
int main()
{
    //freopen("tt.in", "r", stdin);
    scanf("%s",s+1);
    int len=strlen(s+1);
    pam.init();
    for(int i=1;i<=len;i++) 
        s[i]=pam.insert(s[i]-'a')+'0';
    s[len+1]='\0';
    printf("%s\n",s+1);
}

APIO2014 Palindromes

题目大意

给你一个由小写拉丁字母组成的字符串 ss。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。
对于给你的这个字符串 ss,求所有回文子串中的最大存在值。

题解

先构造出回文自动机。构建的时候多维护数组siz,siz表示以每个字符结尾的最长回文串的出现次数。
观察回文自动机,从son指针看,可以发现这是一颗树结构,满足下层节点长度大于上层节点,从fail指针看也是这样。
这道题就要用到fail指针的性质。
我们从后往前(就是从底层往上)扫描,对于第一个节点,假设siz[i]=x那么九说明这个串出现了x次,更新答案。
然后,如果这个节点有fail节点,那么还要让siz[fail[i]]+=siz[i],这是因为每有一个i节点对应的串,就会有一个fail[i]节点对应的串,而fail[i]节点在构造的时候并没有加上这部分的siz。

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 300005
struct PAM
{
    int son[N][26],fail[N],len[N],s[N],val[N],n,last,tot;
    long long ans;
    void init(){len[tot=fail[0]=fail[1]=1]=-1;s[0]=-1;}
    int find(int x){while(s[n-len[x]-1]!=s[n]) x=fail[x];return x;}
    void insert(int x)
    {
        s[++n]=x;
        int p=find(last);
        if(!son[p][x])
        {
            len[++tot]=len[p]+2;
            fail[tot]=son[find(fail[p])][x];
            son[p][x]=tot;
        }
        val[last=son[p][x]]++;
    }
    void solve()
    {
        for(int i=tot;i>1;i--)
        {
            ans=max(ans,1ll*val[i]*len[i]);
            val[fail[i]]+=val[i];
        }
        printf("%lld\n",ans);
    }
}pam;
char s[N];
int len;
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%s",s);len=strlen(s);
    pam.init();
    for(int i=0;i<len;i++) pam.insert(s[i]-'a');
    pam.solve();
}

HDU5421Victor and String

题目大意

题解

如果删掉操作1就和上一题差不多了是吧。
3怎么做?有多少个节点就有多少个不同的回文串。
4怎么做?给每个节点定义一个深度dep,就是这个节点到空串的沿fail指针的距离,那么新建一个节点多出来的回文串就是dep[i]个
对于1操作,我们也维护一个last,设为_last吧。
我们发现,只有在整个串变成回文串的时候才会影响到last,同理,last也只会在整个串变成回文串的时候影响到_last,这样我们几乎可以互不相干的在同一个自动机上维护两个last,添加字符什么的都差不多,就是find函数有一点区别,一个是从前往后,一个从后往前。fail,len,dep都是相同的。只有当len[last]或者len[_last]变成整个串长度时把另一个last(_last)也改成这个_last(last)。
我开始在纠结要不要维护两套fail,毕竟前后不太一样啊,后来我发现我SB了,代表的串都一样fail怎么可能不一样呢……

我的程序

#include <bits/stdc++.h>
using namespace std;
char getc()
{    
    static char *S,*T,buf[65536];
    if(S==T){T=(S=buf)+fread(buf,1,65536,stdin);if(S==T) return EOF;}
    return *S++;
}
int read()
{
    static char ch;static int D,f;
    while(!isdigit(ch=getc())&&ch!='-');
       if(ch=='-') ch=getc(),f=1;else f=0;
    for(D=ch-'0';isdigit(ch=getc());) D=D*10+ch-'0';
    return f?D:-D;
}
#define N 200005
struct PAM
{
    int last[2],tot,n,_n;
    int fail[N],son[N][26],len[N],s[N],dep[N];
    long long sum;
    void init()
    {
        memset(son[0],0,sizeof(son[0]));
        memset(son[1],0,sizeof(son[1]));
        memset(s,-1,sizeof(s));
        tot=1;last[0]=last[1]=0;sum=0;
        fail[1]=fail[0]=1;len[0]=0;len[1]=-1;
        n=100000;_n=100001;
    }
    int find(int x,int d)
    {
        if(d==0) while(s[n-len[x]-1]!=s[n]) x=fail[x];
        else while(s[_n+len[x]+1]!=s[_n]) x=fail[x];
        return x;
    }
    void insert(int x,int d)
    {
        if(!d) s[++n]=x;
        else s[--_n]=x;
        int p=find(last[d],d);
        if(!son[p][x])
        {
            len[++tot]=len[p]+2;
            memset(son[tot],0,sizeof(son[tot]));
            fail[tot]=son[find(fail[p],d)][x];
            dep[tot]=dep[fail[tot]]+1;
            son[p][x]=tot;
        }
        last[d]=son[p][x];
        if(len[last[d]]==n-_n+1) last[d^1]=last[d];
        sum+=dep[last[d]];
    }
}pam;
int n,op;
char s[3];
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
    #endif
    while(cin>>n)
    {
        pam.init();
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&op);
            if(op<=2) 
            {
                scanf("%s",s);
                pam.insert(s[0]-'a',op-1);
            }
            else if(op==3) printf("%d\n",pam.tot-1);
            else printf("%lld\n",pam.sum);
        }
    }
}

基因合成

题目大意

题解

考虑到一个串要么是一个一个加进来的,要么是一个经过翻转的回文串再在旁边加字符得到的。
所以说得到一个串需要的次数只可以用这个串包含的回文串更新。
于是我们把最后的串建立回文自动机,现在要求出得到每个回文串所需要的最小次数。
一个回文串会被如下几种情况更新,设回文范围为[l,r]之间的间隔。
1.一个范围[mid+x,r],x>0的回文串。
2,.一个范围在[mid+x,r-y],x>=0,y>=0内的回文串
且最后一次操作一定是第二种操作。
第一种情况,我们在维护回文自动机的时候,还需要维护一个trans指针,指向小于这个串长度的一半的最长回文后缀,就是多往上跑几步fail,直到长度小于一半。
第二种情况,直接在自动机上沿son指针向下传就可以了。
然后我们在自动机上进行树形dp。用f[x]表示得到节点x代表的回文串需要的次数。
长度为奇数的回文串的f先设为串长,对于一个已经求出的节点x,枚举他的儿子,如果存在,则
f[son]=f[x]+1,而f[son]还可以用son的trans更新。
这样从上往下扫一遍就可以了。
为什么是对的呢?首先trans更新的那里一定是对的。
那么沿son下传一定能更新到正确答案吗?如果一个节点的f是用一个范围在[mid+x,r-y],x>=0,y>=0内的回文串更新得到的,那么这个节点在之前一定已经通过trans更新过了[l+y,r-y],然后[l+y,r-y]这个串再沿着son指针扩展就能更新到[l,r]了~

我的程序

#include <bits/stdc++.h>
using namespace std;
#define N 200005
int T,n;
char s[N];
int rk[100];
struct Palindrome_Automaton
{
    int son[N][4],fail[N],trans[N],len[N],s[N],tot,last,l;
    int dp[N],q[N],f,t,ans;
    void init()
    {
        memset(son[0],0,sizeof(son[0]));
        memset(son[1],0,sizeof(son[1]));
        tot=1;last=0;
        fail[0]=fail[1]=1;
        len[0]=0;len[1]=-1;
        s[l=0]=-1;
    }
    int get_pos(int x)
    {
        while(s[l-len[x]-1]!=s[l]) 
            x=fail[x];
        return x;
    }
    void insert(int x)
    {
        s[++l]=x;
        int now=get_pos(last);
        if(!son[now][x])
        {
            len[++tot]=len[now]+2;
            memset(son[tot],0,sizeof(son[tot]));
            fail[tot]=son[get_pos(fail[now])][x];
            if(len[tot]<=2) trans[tot]=fail[tot];
            else
            {
                int tmp=trans[now];
                while(s[l-len[tmp]-1]!=s[l]||(len[tmp]+2)*2>len[tot]) 
                    tmp=fail[tmp];
                trans[tot]=son[tmp][x];
            }
            son[now][x]=tot;
        }
        last=son[now][x];
    }
    void work()
    {
        ans=l;dp[0]=1;
        for(int i=0;i<=tot;i++) 
        if(len[i]&1) dp[i]=len[i];
        q[f=t=1]=0;
        while(f<=t)
        {
            int x=q[f++];
            for(int tmp,k=0;k<4;k++)
            if(tmp=son[x][k])
            {
                dp[tmp]=dp[x]+1;
                dp[tmp]=min(dp[tmp],len[tmp]/2-len[trans[tmp]]+dp[trans[tmp]]+1);
                ans=min(ans,l-len[tmp]+dp[tmp]);
                q[++t]=tmp;
            }
        }
        printf("%d\n",ans);
    }
}pam;
int main()
{
    freopen("dna.in", "r", stdin);
    freopen("dna.out", "w", stdout);
    rk['A']=0;rk['C']=1;rk['G']=2;rk['T']=3;
    for(cin>>T;T--;)
    {
        scanf("%s",s+1);n=strlen(s+1);
        pam.init();
        for(int i=1;i<=n;i++) 
            pam.insert(rk[s[i]]);
        pam.work();
    }
    fclose(stdin);
    fclose(stdout);
    return 0;
}