题目分类：状态压缩动态规划

题意：

给出n个字符串，求他们的最短公共母串。

题解：

可以发现串的数量很少，可以使用状态压缩动态规划dp[mask][i]表示当前使用过的字符串为mask，最后一个为i的情况下最短母串长度是多少，同时需要记录每个状态的转移，在转移的时候要把字符串生成出来来决策使用哪个转移。

程序；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char str[20][100];
int n,leng[20],ind[20];
int a[20][20];
int dp[4100][14];
int trace[4100][14];
struct node2
{
	int len;
	char st[700];
	inline void update(int x,int las)
	{
		len+=leng[x];
		len-=a[las][x];
		for (int i=a[las][x]+1;i<=leng[x];i++)
		{
			st[len-leng[x]+i]=str[x][i];
		}
	}
}ans,tmp1,tmp2;
inline bool over(const node2&x,const node2&y)
{
	if(x.len==0)return false;
	if(y.len==0)return true;
	if(x.len!=y.len)return x.len<y.len;
	for (int i=1;i<=x.len;i++)
	{
		if(x.st[i]!=y.st[i])return x.st[i]<y.st[i];
	}
	return false;
}
inline bool cover(int x,int y)
{
	if(leng[x]<leng[y])return false;
	for (int i=1;i<=leng[x]-leng[y]+1;i++)
	{
		int fl=0;
		for (int j=1;j<=leng[y];j++)
		{
			if(str[x][i+j-1]!=str[y][j])fl=1;
		}if(fl==0)return true;
	}return false;
}
inline int junc(int x,int y)
{
	for (int i=min(leng[x],leng[y]);i>=1;i--)
	{
		int fl=0;
		for (int j=1;j<=i;j++)
		{
			if(str[x][leng[x]-i+j]!=str[y][j])fl=1;
		}
		if(fl==0)return i;
	}return 0;
}
int cnt,useful[20];
inline void findans(int mask,int x)
{
	if(mask==0)return;
	findans(mask-(1<<(x-1)),trace[mask][x]);
	ans.update(useful[x],useful[trace[mask][x]]);
}
inline void findtmp1(int mask,int x)
{//printf("1:%d %d\n",mask,x);
	if(mask==0)return;
	findtmp1(mask-(1<<(x-1)),trace[mask][x]);
	tmp1.update(useful[x],useful[trace[mask][x]]);
}
inline void findtmp2(int mask,int x)
{//printf("2:%d %d\n",mask,x);
	if(mask==0)return;
	findtmp2(mask-(1<<(x-1)),trace[mask][x]);
	tmp2.update(useful[x],useful[trace[mask][x]]);
}
inline bool alphamin(int x,int y)
{
	for (int i=1;i<=min(leng[x],leng[y]);i++)
	{
		if(str[x][i]!=str[y][i])return str[x][i]<str[y][i];
	}
	return leng[x]<leng[y];
}
inline bool cmp(int x,int y)
{
	return alphamin(x,y);
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",str[i]+1);
		leng[i]=strlen(str[i]+1);
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if(i!=j&&cover(j,i)&&leng[i]!=leng[j])ind[i]=1;
			a[i][j]=junc(i,j);//printf("%d-%d %d\n",i,j,a[i][j]);
		}
	}
	for (int i=1;i<=n;i++)
	{
		if(ind[i]==0)
		{
			cnt++;
			useful[cnt]=i;
		}
	}
	sort(useful+1,useful+cnt+1,cmp);
	for (int i=1;i<=cnt;i++)
	{
		dp[(1<<(i-1))][i]=leng[useful[i]];
	}
	for (int i=1;i<(1<<cnt)-1;i++)
	{
		for (int j=1;j<=cnt;j++)
		{
			if(dp[i][j]==0)continue;
			if((i&(1<<(j-1)))==0)continue;
			for (int k=1;k<=cnt;k++)
			{
				if((i&(1<<(k-1)))!=0)continue;
				int tmp=dp[i][j]+leng[useful[k]]-a[useful[j]][useful[k]];
				if(dp[i|(1<<(k-1))][k]==0||tmp<dp[i|(1<<(k-1))][k])
				{
					dp[i|(1<<(k-1))][k]=tmp;
					trace[i|(1<<(k-1))][k]=j;
				}
				else
				{
					tmp1.len=0;
					tmp2.len=0;
					findtmp1((i|(1<<(k-1))),k);
					findtmp2(i,j);
					tmp2.update(useful[k],useful[j]);
					if(over(tmp2,tmp1))
					{
						trace[i|(1<<(k-1))][k]=j;
					}
				}
			}
		}
	}
	int tmp=1;
	tmp1.len=0;
	findtmp1((1<<cnt)-1,1);
	for (int i=2;i<=cnt;i++)
	{
		tmp2.len=0;
		findtmp2((1<<cnt)-1,i);
		if(dp[(1<<cnt)-1][i]<dp[(1<<cnt)-1][tmp]||over(tmp2,tmp1))
		{
			tmp=i;
			tmp1=tmp2;
		}
	}
	for (int i=1;i<=tmp1.len;i++)
	{
		printf("%c",tmp1.st[i]);
	}printf("\n");
	return 0;
}