526互联

luogu P2322 [HNOI2006] 最短母串问题

发布时间 2023-09-09 06:38:56作者: Trmp

luogu P2322 [HNOI2006] 最短母串问题

题目链接

思路比较的简单的 dp 题。

首先看数据范围，\(n \leqslant 12,len\leqslant50\) 应该是状压没跑了。

考虑设 \(f_{i,j}\) 表示在选择集合 \(j\) 且，尾部的字符串为第 \(i\) 个的最短长度。

考虑两个字符串重合的部分，设 \(len_{i,j}\) ,表示 \(i\) 在前，\(j\) 在后时的最长公共前后缀长度，这个可以用 \(KMP\) 预处理出来。注意在两字符串相加时，为了防止匹配超过原长，可以在两字符串之间加一个奇怪的字符，以防止匹配错误。

然后状态转移方程显然。

\[f_{k,j|(1<<(k-1)} = \min (f_{i,j}+size_k-len_{i,k}) \]

至于如何输出字典序最小的串，可以设 \(g_{i,j}\) 表示在当前状态下的长度最短的字典序最小的串，和 \(f_{i,j}\) 一起转移就行了。

一些细节，可以先用 AC自动机 去重，去除串与串之间包含的情况。

复杂度 \(O(n^22^n)\)

代码 
#include <iostream>
#include <cstdio>
#include <queue>
#include <cmath>
#include <vector>
#include <cstring>
#include <algorithm>

const int M=100000;
const int N=15;
const int L=60;
const int inf=2e9;

using namespace std;

inline int read() {
    int f=1,x=0;
    char ch=getchar();
    while(ch>'9' || ch<'0') {
        if(ch=='-') {
            f=-1;
        }
        ch=getchar();
    }
    while(ch>='0' && ch<='9') {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,cnt,tot;
int le[N][N],nxt[L<<1],l[N];
int f[N][(1<<N)];
string s[N],a[N],g[N][1<<N],ans[M];

struct Tire {
    int fail,end;
    int son[26];
}tr[M];
bool vis[N];

void insert(string ss,int id) {
    int len=ss.size(),now=0;
    for(int i=0;i<len;i++) {
        int ch=ss[i]-'A';
        if(!tr[now].son[ch]) {
            tr[now].son[ch]=++cnt;
        }
        now=tr[now].son[ch];
    }
    if(!tr[now].end) tr[now].end=id;
    else vis[id]=1;
}

void get_fail() {
    queue <int> q;
    for(int i=0;i<26;i++) {
        if(tr[0].son[i]) {
            q.push(tr[0].son[i]);
        }
    }

    while(!q.empty()) {
        int now=q.front();
        q.pop();
        for(int i=0;i<26;i++) {
            int v=tr[now].son[i];
            if(v) {
                tr[v].fail=tr[tr[now].fail].son[i];
                q.push(v);
            }
            else {
                tr[now].son[i]=tr[tr[now].fail].son[i];
            }
        }
    }
}

void query(string ss,int id) {
    if(vis[id]) return;
    int len=ss.size(),now=0;
    for(int i=0;i<len;i++) {
        int ch=ss[i]-'A';
        now=tr[now].son[ch];

        int tmp=now;
        while(tmp) {
            vis[tr[tmp].end]=1;
            tmp=tr[tmp].fail;
        }
    }
    vis[id]=0;
}

int KMP(string ss) {
    int len=ss.size();
    for(int i=0;i<=len;i++) {
        nxt[i]=0;
    }
    for(int i=2,j=0;i<len;++i) {
        while(j && ss[j+1]!=ss[i]) j=nxt[j];
        if(ss[j+1]==ss[i]) j++;
        nxt[i]=j;
    }
    return nxt[len-1];
}

void init() {
    get_fail();
    for(int i=1;i<=n;i++) query(s[i],i);
    for(int i=1;i<=n;i++) {
        if(!vis[i]) a[++tot]=s[i];
    }
    n=tot;
    for(int i=1;i<=n;i++) l[i]=a[i].size();

    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) continue;
            string ss=" "+a[j]+"|"+a[i];
            le[i][j]=KMP(ss);
        }
    }
}

int main() {

    n=read();
    for(int i=1;i<=n;i++) {
        cin>>s[i];
        insert(s[i],i);
    }
    init();

    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++) {
        f[i][(1<<(i-1))]=l[i];
        g[i][(1<<(i-1))]=a[i];
    }
    f[0][0]=0;

    for(int i=1;i<(1<<n);i++) {
        for(int j=1;j<=n;j++) {
            if(((1<<(j-1)) & i)) {
                for(int k=1;k<=n;k++) {
                    if(!((1<<(k-1)) & i)) {
                        int len=le[j][k],to=i|(1<<(k-1));
                        string ss=g[j][i]+a[k].substr(len,l[k]);
                        
                        if((f[j][i]+l[k]-len < f[k][to]) ||
                        (f[j][i]+l[k]-len==f[k][to] && g[k][to]>ss)) {
                            f[k][to]=f[j][i]+l[k]-len;
                            g[k][to]=ss;
                        }
                    }
                }
            }
        }
    }
    
    int mi=inf,sum=0;
    for(int i=1;i<=n;i++) mi=min(mi,f[i][(1<<n)-1]);
    for(int i=1;i<=n;i++) {
        if(mi==f[i][(1<<n)-1]) {
            ans[++sum]=g[i][(1<<n)-1];
        }
    }
    sort(ans+1,ans+sum+1);
    cout<<ans[1];

	return 0;
}