- 单词接龙
- 2016-11-09 17:40:42 @
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<string.h>
using namespace std;
char a[21][119];
int num[21][21],l[21];
int aa[21];
int n;
int maxi=0;
int gets(int q,int p)
{
if(q==n+1){
if(a[q][0]==a[p][0]) return 1;
else return 0;
}
else if(q==p){
int w=0,tol=0;
int i,j;
for(i=l[q]-1;i>0;i--){
if(a[q][i]==a[p][w]){
for(j=i;j<l[q];j++){
if(a[q][j]==a[p][w]){
tol++;
w++;
}
else{
w=tol=0;
break;
}
}
if(j==l[q]) return tol;
}
}
return 0;
}
else{
int w=0,tol=0;
int i,j;
for(i=l[q]-1;i>0;i--){
if(a[q][i]==a[p][w]){
for(j=i;j<l[q];j++){
if(a[q][j]==a[p][w]){
tol++;
w++;
}
else{
w=tol=0;
break;
}
}
if(j==l[q]){
if(tol>=l[q]||tol>=l[p]) return 0;
else return tol;
}
}
}
return 0;
}
}
int search(int m,int length){
for(int i=1;i<=n;i++){
if(aa[i]<2&&num[m][i]!=0){
aa[i]++;
search(i,length+l[i]-num[m][i]);
aa[i]--;
}
}
if(length>maxi) maxi=length;
return 0;
}
int main(){
// freopen("dcjl.in","r",stdin);
// freopen("dcjl.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
l[i]=strlen(a[i]);
}
cin>>a[n+1];
for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++)
num[i][j]=gets(i,j);
/* for(int i=1;i<=n+1;i++)
for(int j=1;j<=n;j++)
printf("%d %d %d\n",i,j,num[i][j]);*/
for(int i=1;i<=n;i++){
if(num[n+1][i]!=0){
aa[i]++;
search(i,l[i]);
aa[i]--;
}
}
cout<<maxi;
return 0;
}