[HNOI2006]最短母串 (AC自动机+状压)

Description

给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。

Input

第一行是一个正整数n（n<=12），表示给定的字符串的个数。

以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.

Output

只有一行，为找到的最短的字符串T。在保证最短的前提下，

如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。

Sample Input

2
ABCD
BCDABC

Sample Output

ABCDABC

拿这题练了练数组版的AC自动机

数据范围显然状压插入时预处理出每个节点是哪个串的结束节点

然后建图连fail指针的时候合并状态

为了最短显然需要按层转移，所以bfs

可以保证一达到末状态就return得到最优解

数组

#include<queue>

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

using namespace std;

int n,tot=;

char s[];

struct trie

{

    int son[],st,fail;

}t[];

void ins(char* str,int k)

{

    int l=strlen(str+),root=;

    for(int i=;i<=l;i++)

    {

        int x=str[i]-'A';

        if(!t[root].son[x])t[root].son[x]=++tot;

        root=t[root].son[x];

    }

    t[root].st|=<<(k-);

}

void build()

{

    queue<int> q;

    for(int i=;i<;i++)

        if(t[].son[i])q.push(t[].son[i]);

    while(!q.empty())

    {

        int x=q.front();

        q.pop();

        for(int i=;i<;i++)

        {

            int &y=t[x].son[i];

            if(!y)

            {

                y=t[t[x].fail].son[i];

                continue;

            }

            t[y].fail=t[t[x].fail].son[i];

            t[y].st|=t[t[y].fail].st;

            q.push(y);

        }

    }

}

bool v[][(<<)+];

int let[(<<)+],fa[(<<)+],ans[],num=;

void bfs()

{

    queue<pair<int,int> > q;

    q.push(make_pair(,));

    int f=,ss=;

    while(!q.empty())

    {

        int x=q.front().first,nowst=q.front().second;

        q.pop();

        if(nowst==(<<n)-)

        {

            for(int i=f;i;i=fa[i])

                ans[++num]=let[i];

            for(int i=num;i;i--)putchar(ans[i]+'A');

            return ;

        }

        for(int i=;i<;i++)

        {

            int y=t[x].son[i],nxtst=nowst|t[y].st;

            if(!v[y][nxtst])

            {

                v[y][nxtst]=;

                ss++;

                fa[ss]=f;

                let[ss]=i;

                q.push(make_pair(y,nxtst));

            }

        }

        f++;

    }

}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%s",s+);

        ins(s,i);

    }

    build();

    bfs();

    return ;

}

指针

#include<cstdio>

#include<iostream>

#include<cstring>

#include<queue>

#include<cstdlib>

using namespace std;

const int N=;

int n;

char s[N];

struct node

{

    node *son[];

    int st;

    bool vis[(<<)+];

    node *fail;

    node()

    {

        memset(this,,sizeof(node));

    }

};

node *root;

void ini()

{

    root=new node();

}

void ins(char *str,int num)

{

    int l=strlen(str+);

    node *now=root;

    for(int i=;i<=l;i++)

    {

        if(!now->son[str[i]-'A'])now->son[str[i]-'A']=new node();

        now=now->son[str[i]-'A'];

    }

    now->st|=<<(num-);

}

void build()

{

    queue<node*>q;

    for(int i=;i<;i++)

    {

        if(root->son[i])

        {

            root->son[i]->fail=root;

            q.push(root->son[i]);

        }

        else root->son[i]=root;

    }

    while(!q.empty())

    {

        node *x=q.front();

        q.pop();

        for(int i=;i<;i++)

        {

            if(x->son[i])

            {

                x->son[i]->fail=x->fail->son[i];

                if(x->son[i]->fail)x->son[i]->st|=x->son[i]->fail->st;

                q.push(x->son[i]);

            }

            else x->son[i]=x->fail->son[i];

        }

    }

}

int fa[],ans[],tot=,qwq[];

void bfs()

{

    queue<node*> q;

    queue<int> ST;

    q.push(root);ST.push();

    root->vis[]=;

    int f=,ss=;

    while(!q.empty())

    {

        node *x=q.front();int nowSt=ST.front();

        q.pop();ST.pop();

    //    cout<<(x->st)<<endl;

        if(nowSt==(<<n)-)

        {

            for(int i=f;i;i=fa[i])ans[++tot]=qwq[i];

            for(int i=tot;i;i--)putchar(ans[i]+'A');

            return ;

        }

        for(int i=;i<;i++)

        {

            if(!x->son[i])continue;

            int state=nowSt|(x->son[i]->st);

            if(!x->son[i]->vis[state])

            {

                x->son[i]->vis[state]=;

                ss++;

                fa[ss]=f;

                qwq[ss]=i;

                q.push(x->son[i]);

                ST.push(state);

            }

        }

        f++;

    }

}

int main()

{

    scanf("%d",&n);

    ini();

    for(int i=;i<=n;i++)

    {

        scanf("%s",s+);

        ins(s,i);

    }

    build();

    bfs();

    return ;

}

（话说这题数组大小神TM坑啊……）

巴特西