[BZOJ1195/Luogu2322][HNOI2006]最短母串(AC自动机,状态压缩动态规划)

发布于 2018-03-24  115 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1195/Luogu2322][HNOI2006]最短母串(AC自动机,状态压缩动态规划)

Description

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

Tag

AC自动机,状态压缩动态规划

解决思路

首先,被其它字符串包含的字符串是不需要考虑的,第一步先去掉这下被包含的字符串。然后考虑假设我们已经知道了剩下的串在构造的串中的出现顺序,
如何得到长度和方案呢?那么就是把每两个相邻的字符串,前面与后面相同的最长前后缀合并,每增加一个串增加的长度就是后一个的长度减去最长相同前后缀。
现在的问题变成了快速地求两个字符串的并,即前一个字符串的后缀和后一个字符串的前缀的最长相同前缀。
考虑在 AC 自动机上解决这个问题。x 串与 y 串的最长相同前后缀其实就是,从 y 串的每一个位置开始跳 fail,当跳到一个 x 串中的节点时,记录这个节点与 x 串末尾对应节点的深度之差,这就代表着从 y 的这个前缀能最长与 x 的这么长的后缀匹配。所有的深度之差中的最大值就是要找的最长匹配,后一个字符串的长度减去这个最长匹配就是加上这个字符串要增加的长度。
数据范围较小,所以你可以暴力地枚举两个字符串然后在 AC 自动机中标记、跳 fail,也可以像在 [NOI2011] 阿狸的打字机那样走一遍 Trie 树,一边走一边标记,一边计算。当然要注意,可能两个字符串根本就没有相同前后缀,这时的代价就是后一个串的长度。
此时,我们得到了任意一个字符串接在另一个任意字符串后面要增加的长度,于是题目转化为,给定两点之间的转移代价,求一条不重不漏经过所有点各一次的最短路径,起点任意。
那么就可以类似旅行商问题中的做法,设 F[i][S] 表示当前在点 i,经过的点集合为 S 的最短路,分别转移即可。注意同时要求字典序最小。
关于字典序最小,开始思路是在Trie树中重新分配一次编号,从小到大,但是由于前后两串有重叠的部分,所以这样出来的字典序不是最小,所以最好的办法还是在转移的时候实时记录当前构造出来的串。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<string>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=15;
const int maxM=maxN*maxN*8;
const int maxL=100;
const int maxAlpha=27;
const int inf=2147483647;

class TrieData
{
public:
    int end,fail,id,depth,input;
    int son[maxAlpha];
    int son2[maxAlpha];
};

class QueueData
{
public:
    int u,key;
};

int n,nodecnt,idcnt,Id[maxN];
bool path[maxN*maxL];
char str[maxN][maxL];
TrieData T[maxN*maxL];
int edgecnt=0,Head[maxN],Next[maxM],V[maxM],W[maxM];
int Dist[maxN][1<<maxN];
string From[maxN][1<<maxN];
bool inqueue[maxN][1<<maxN];
int Map[maxN][maxN];
queue<QueueData> Q;

void Insert(char *str,int id);
void GetFail();
void dfs1(int u);
void dfs2(int u);
void Add_Edge(int u,int v,int w);
void Add(int u,int v,int w);

int main()
{
    mem(Head,-1);mem(Map,-1);
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",str[i]+1);
        Insert(str[i],i);//输入字符串并加入AC自动机
    }
    GetFail();//构建Fail指针
    dfs1(0);
    for (int i=1;i<=idcnt;i++)
        for (int j=1;j<=idcnt;j++)
            Map[i][j]=T[Id[j]].depth;//初始化长度
    dfs2(0);//得到任意两串之间的距离
    for (int i=1;i<=idcnt;i++)
        for (int j=1;j<=idcnt;j++)
            if (Map[i][j]!=-1) Add(i,j,Map[i][j]);
    mem(Dist,63);//初始化最短路
    for (int i=1;i<=idcnt;i++)//加入最短路
    {
        Dist[i][1<<(i-1)]=T[Id[i]].depth;
        Q.push((QueueData){i,1<<(i-1)});
        inqueue[i][1<<(i-1)]=1;
        int l=strlen(str[T[Id[i]].input]+1);
        for (int j=1;j<=l;j++) From[i][1<<(i-1)]+=str[T[Id[i]].input][j];
    }
    do//求解最短路,注意要求字典序最小
    {
        int u=Q.front().u,key=Q.front().key;Q.pop();
        for (int i=Head[u];i!=-1;i=Next[i])
        {
            if (((1<<(V[i]-1))&key)!=0) continue;
            int v=V[i],kk=key|(1<<(V[i]-1));
            int d=Dist[u][key]+W[i];
            string ss=From[u][key];
            int len=strlen(str[T[Id[V[i]]].input]+1);
            for (int j=len-W[i]+1;j<=len;j++) ss+=str[T[Id[V[i]]].input][j];
            if ((Dist[v][kk]>d)||((Dist[v][kk]==d)&&(ss<From[v][kk])))
            {
                Dist[v][kk]=d;From[v][kk]=ss;
                if (inqueue[v][kk]==0)
                {
                    inqueue[v][kk]=1;
                    Q.push((QueueData){v,kk});
                }
            }
        }
        inqueue[u][key]=0;
    }
    while (!Q.empty());
    int Ans=inf;
    string ansstring;//求最小值
    for (int i=1;i<=idcnt;i++)
        if ((Ans>Dist[i][(1<<idcnt)-1])||((Ans==Dist[i][(1<<idcnt)-1])&&(ansstring>From[i][(1<<idcnt)-1])))
        {
            Ans=Dist[i][(1<<idcnt)-1];
            ansstring=From[i][(1<<idcnt)-1];
        }
    int sz=ansstring.size();
    for (int i=0;i<sz;i++) printf("%c",ansstring[i]);
    printf("\n");
    return 0;
}

void Insert(char *str,int id)
{
    int len=strlen(str+1);
    int now=0;
    for (int i=1;i<=len;i++)
    {
        if (T[now].son[str[i]-'A']==0) T[now].son[str[i]-'A']=T[now].son2[str[i]-'A']=++nodecnt;
        now=T[now].son[str[i]-'A'];
    }
    T[now].end=1;T[now].input=id;
    return;
}

int Queue[maxN*maxL];

void GetFail()
{
    int h=0,t=0;
    for (int i=0;i<maxAlpha;i++) if (T[0].son[i]) Queue[++h]=T[0].son[i];
    while (t!=h)
    {
        int u=Queue[++t];
        for (int i=0;i<maxAlpha;i++)
            if (T[u].son2[i])
            {
                T[T[u].son2[i]].fail=T[T[u].fail].son2[i];
                Queue[++h]=T[u].son2[i];
            }
            else T[u].son2[i]=T[T[u].fail].son2[i];
    }
    for (int i=nodecnt;i>=0;i--) T[T[i].fail].end=0;
    return;
}

void dfs1(int u)
{
    if (T[u].end) T[u].id=++idcnt,Id[idcnt]=u;
    for (int i=0;i<maxAlpha;i++) if (T[u].son[i]) T[T[u].son[i]].depth=T[u].depth+1,dfs1(T[u].son[i]);
    return;
}

void dfs2(int u)
{
    path[u]=1;
    if (T[u].end)
    {
        for (int i=1;i<=idcnt;i++)
        {
            if (i==T[u].id) continue;
            int now=Id[i];
            while (now!=0)
            {
                if (path[now])
                {
                    Add_Edge(i,T[u].id,T[u].depth-T[now].depth);
                }
                now=T[now].fail;
            }
        }
    }
    for (int i=0;i<maxAlpha;i++) if (T[T[u].son[i]].depth==T[u].depth+1) dfs2(T[u].son[i]);
    path[u]=0;
    return;
}

void Add_Edge(int u,int v,int w)//由于有大量重边,所以为了减少边的数量,这里先取最小值,最后再加边进去
{
    if ((Map[u][v]==-1)||(Map[u][v]>w)) Map[u][v]=w;
    return;
}

void Add(int u,int v,int w)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;W[edgecnt]=w;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ1195/Luogu2322][HNOI2006]最短母串(AC自动机,状态压缩动态规划)


HNCJ OIer