POJ - 3080 Blue Jeans解题报告

对于第一个串，按照从长到短的顺序枚举它的所有可能子串（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;}