描述
程序员常常需要给变量命名、给函数命名、给项目命名、给团队命名…… 好的名字可以大大提高程序员的主观能动性，所以很多程序员在起名时都会陷入纠结和烦恼。
小Hi希望给新的项目起个拉风的名字。他希望这个名字可以包含N个关键字，并且总长度最短。例如包含关键字abcd、cdab和dabc的最短字符串是cdabcd。
给定N个关键字，请你帮小Hi找到最短的包含所有关键字的字符串。输出这个字符串的长度。
输入
第一行包含一个整数N。(1 <= N <= 15)
以下N行每行包含一个只包含小写字母的字符串。字符串长度不超过100。
输出
输出最短的长度。
样例输入
3 abcd cdab dabc
样例输出
6
思路：DP，我们假设已经合并成字符串S，若把str加到末尾，不知道对齐哪一位最优，假设str长度为len，可能对其位数<len，也可能>=len，即覆盖掉前面一个str’。
所以，需要我们预处理包含关系的字符串，删去被包含的字符串，那么就可以DP了。
具体的，dp[2^15][15]表示使用的哪些字符串，最后一个串是哪个，当然，前提是删去了被包含的字符串。
下面是自己写的AC自动机的代码，但是有些错误。。。。
#include<queue> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=50000; const int inf=0x7fffffff; int dp[1600][1<<15]; struct in { int dis,pos,opt; in(int x,int y,int z):dis(x),pos(y),opt(z){} friend bool operator < (in a,in b){ return a.dis>b.dis; } }; priority_queue<in>q; int Next[maxn],ch[maxn][26],End[maxn],N,cnt; int que[maxn],head,tail; char s[maxn]; struct ACauto { void insert(int tag) { int Now=0; for(int i=0;s[i];i++){ if(!ch[Now][s[i]-'a']) ch[Now][s[i]-'a']=++cnt; Now=ch[Now][s[i]-'a']; } End[Now]=1<<tag; } void build() { for(int i=0;i<26;i++){ if(ch[0][i]) que[++head]=ch[0][i]; } while(tail<head){ int u=que[++tail]; for(int i=0;i<26;i++){ if(ch[u][i]){ que[++head]=ch[u][i]; Next[ch[u][i]]=ch[Next[u]][i]; End[ch[u][i]]|=End[Next[ch[u][i]]]; } else ch[u][i]=ch[Next[u]][i]; } } } void solve() { dp[0][0]=0; q.push(in(0,0,0)); while(!q.empty()){ in tmp=q.top(); q.pop(); int u=tmp.pos, k=tmp.opt; for(int i=0;i<26;i++){ int v=ch[u][i],kk=k|End[v]; if(v==0) continue; if(kk==(1<<N)-1) { printf("%d ",dp[u][k]+1); return ; } if(dp[v][kk]>dp[u][k]+1) { dp[v][kk]=dp[u][k]+1; q.push(in(dp[v][kk],v,kk)); } } } } }Trie; int main() { scanf("%d",&N); for(int i=0;i<N;i++){ scanf("%s",s); Trie.insert(i); } Trie.build(); for(int i=0;i<=cnt;i++) for(int j=0;j<(1<<N);j++) dp[i][j]=inf; Trie.solve(); return 0; }