当前位置： 移动技术网 > IT编程>开发语言>C/C++ > [CERC2014] Virus synthesis

[CERC2014] Virus synthesis

2019年01月04日  | 移动技术网IT编程  | 我要评论

超神学院神与神,摄影团,电视剧十二生肖传奇

设f[i]为形成极长回文串i的最小操作数。答案为min f[i]+n-len[i]。
在不形成偶回文的情况下形成奇回文的最小操作数为该串长度。可以不考虑（但ans赋为len）。

正确性基于：
1）奇、偶回文嵌套形成最终的偶回文一定可以转化为由在不形成奇回文的情况下形成偶回文。
2）奇、偶回文嵌套形成最终的奇回文并不需要讨论。

也不知道理解对没有。。。

所以，以下的回文串皆代指偶回文。

转移1：f[i]=f[j]+1 | 在极长回文串j前后补上一对相同字符可得到i。
举例：
aabbaa : a aa aab aabbaa
caabbaac: a aa aab caab caabbaac
统一化：f[偶根]=1 => f["aa"]=2

转移2：f[i]=min f[j]+1+len[i]/2-len[j] | j=tmp[i].
举例：
abba : a ab abba
abbaccabba: abba abbac abbaccabba

#include <bits/stdc++.h>
using namespace std;
const int n=3e5+10;

map<char,int> tr={
    {'a',0},{'g',1},{'c',2},{'t',3}
};

struct pam_ {
    char *str;
    int last,size;
    int tmp[n],len[n],fail[n],ch[n][26];
    int getfail(int x,int n) {
        while(str[n]!=str[n-len[x]-1]) x=fail[x];
        return x;
    }
    void build(char *bstr) {
        str=bstr;
        str[0]=-1;
        len[1]=-1;
        fail[0]=1;
        last=0;
        size=1;
        memset(ch[0],0,sizeof ch[0]);
        memset(ch[1],0,sizeof ch[1]);
        for(int i=1; str[i]; ++i) {
            int c=tr[str[i]];
            int p=getfail(last,i);
            if(!ch[p][c]) {
                int q=++size;
                memset(ch[q],0,sizeof ch[q]);
                len[q]=len[p]+2;
                fail[q]=ch[getfail(fail[p],i)][c]; 
                ch[p][c]=q;
                if(len[q]<=2) tmp[q]=fail[q];
                else {
                    int x=tmp[p];
                    while(str[i]!=str[i-len[x]-1]||(len[x]+2)*2>len[q]) x=fail[x];
                    tmp[q]=ch[x][c];
                }
            }
            last=ch[p][c];
        }
    }
    int calc() {
        static int que[n];
        static int f[n];
        int n,ans,hd,tl;
        n=ans=strlen(str+1);
        que[hd=0,tl=1]=0;
        for(int i=2; i<=size; ++i) {
            f[i]=len[i];
        }
        f[0]=1,f[1]=0;
        while(hd<tl) {
            int x=que[++hd];
            for(int i=0; i<4; ++i) {
                int y=ch[x][i];
                if(!y) continue;
                f[y]=f[x]+1;
                que[++tl]=y;
                f[y]=min(f[y],f[tmp[y]]+1+len[y]/2-len[tmp[y]]);
                ans=min(ans,f[y]+n-len[y]);
            }
        }
        return ans;
    }
} pam;

int main() {
    int t;
    scanf("%d",&t);
    static char str[n];
    while(t--) {
        scanf("%s",str+1);
        pam.build(str);
        // puts("built");
        printf("%d\n",pam.calc());
    }
    return 0;
}

您可能感兴趣的文章:

如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网