/* 两两求出字符串之间最大可以匹配的值 由已知状态推导出位置状态 状态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 ",ans); } }