對于第一個串，按照從長到短的順序枚舉它的所有可能子串（60*60）對每個子串，判斷在其他的字符串中是否含有此子串。時間復雜度：枚舉第一串的每一個子串60*60/2；在另一個字符串中找是否存在該子串（KMP）60+60（最大）；十個字符串；復雜度為：60*60*10*（60+60）。這個題用kmp算法，看了好久才看懂，回來再要在復習一下kmp，感覺確定next數組的思路有點像數學歸納法或者叫動態規劃。另外就是這道題如果有多個相同長度的答案，需要輸出字典序最小的。因為這個，第一次交沒有ac，然后就是程序應該還是特別難看，一直打補丁，尤其是找到第二個相同長度的公共子串的時候要根據字典序大小判斷是否需要替換的時候，寫的有點亂。。。。 

#include<iostream>#include<stdio.h>#include<string.h>#define N 70using namespace std;char c[15][N]={0};int next[N]={0};int n;void ceshi1(char a[]){	for(int i=0;i<strlen(a);i++)	cout<<next[i];	cout<<endl;}void my_next(char a[])//對于字符串a，把他的每個字符對應的next值計算出來 {	memset(next,0,sizeof(next));	next[0]=-1;	int j=0,k=-1;	while(j<strlen(a))	{		if(k!=-1&&a[j]!=a[k])		{			k=next[k];			continue;		}		k++;j++;		if(a[k]==a[j])next[j]=next[k];		else next[j]=k;	}	}bool my_kmp(char s[],char t[])//r如果s中含有t，則返回1，否則返回0 {	int flag=0;	int i=0,j=0;//i指s，j指t 	while(1)	{		if(s[i]==t[j])		{			if(j==strlen(t)-1)return 1;			i++;j++;			continue;		}		i=i-next[j];		j=0;		if(strlen(s)-i<strlen(t))return 0;	}}void input(){	cin>>n;	char l;	l=getchar();	for(int i=1;i<=n;i++)	{		scanf("%s",c[i]);	}}int main(){	int test;	cin>>test;	while(test--)	{		char s[N]={0};				input();		int max=0;		for(int i=1;i<strlen(c[1]);i++)		{			for(int j=0;j<i;j++)			{				bool flag=1;				char x[N]={0};				int z=0;				for(int t=j;t<=i;t++)				{					x[z]=c[1][t];					z++;				}				for(int t=2;t<=n;t++)				{					my_next(x);					if(!my_kmp(c[t],x))					{						flag=0;break;					}				}				if(flag==1&&strlen(x)>=max)				{					bool ss=0;					if(strlen(x)==max)					{						int ii=0;int jj=0;						while(ii<max)						{							if(s[ii]>x[jj])							{								ss=0;break;								}							if(s[ii]<x[jj])							{								ss=1;break;							}							ii++;jj++;						}					}					if(ss==0)					{						max=strlen(x);						for(int t=0;t<max;t++)						{							s[t]=x[t];						}					}				}			}		}		if(max<3)cout<<"no significant commonalities"<<endl;		else		{			for(int i=0;i<max;i++)			cout<<s[i];			cout<<endl;		}	}				return 0;}