/*
两两求出字符串之间最大可以匹配的值
由已知状态推导出位置状态
状态s表示已经加入到集合中的字符串，0表示串i不存在，1存在
由于字符串的加入顺序会影响结果，所以增加一维来表示
dp[S][i]表示状态集合为S，且i是新加入S的字符串的最大值
*/
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
char a[
15][
15];
int dp[
1<<
11][
15],w[
15][
15],n;
void get(
int x,
int y)
{
w[x][y]=w[y][x]=
0;
int l1=strlen(a[x]),l2=strlen(a[y]),s=
0;
for(
int i=
0; i<l1; i++
)
for(
int j=
0; j<l2; j++
)
{
int k=
0;
s=
0;
while(i+k<l1&&j+k<
l2)
{
if(a[x][i+k]==a[y][j+
k])
s++
;
k++
;
}
if(s>w[x][y])w[x][y]=w[y][x]=
s;
}
}
int main(){
while(cin>>
n,n){
for(
int i=
1;i<=n;i++
)
cin>>
a[i];
for(
int i=
1;i<=n;i++
)
for(
int j=i+
1;j<=n;j++
)
get(i,j);
//得到i和j配对的最大值
memset(dp,0,
sizeof dp);
for(
int i=
0;i<(
1<<n);i++
)
for(
int j=
1;j<=n;j++){
//枚举状态中存在的字符串作为旧状态中最后放进去的字符串
if( !(i&(
1<<(j-
1))) )
continue;
for(
int k=
1;k<=n;k++)
//枚举每个不在状态中的字符串作为新状态中最后放进去的字符串
if(!(i&(
1<<(k-
1))))
dp[i|(
1<<(k-
1))][k]=max(dp[i|(
1<<(k-
1))][k],dp[i][j]+
w[j][k]);
}
int ans=
0;
for(
int i=
1;i<=n;i++
)
ans=max(ans,dp[(
1<<n)-
1][i]);
printf("%d\n",ans);
}
}
转载于:https://www.cnblogs.com/zsben991126/p/10364746.html
