poj3080-kmp+枚举子串 求最长公共子串

因为一直有事这道题又有点繁琐， 所以写了好多天今天才AC，不过1A还是很爽的。

思路还是很简单的，对第一个主串枚举其所有子串，然后将每个子串都与其他的所以主串KMP匹配，如果是所有主串的公共子串则记录 并选出最大的一个  注意这道题要字典序最小

 

代码：

#include "iostream"
using namespace std;
#define  maxsize   80
char c[11][maxsize];
char substring[maxsize];
int next[11][maxsize];
char cans[maxsize];

void getnext(int  n,int length)
{
	
	int  i=0,j=-1;
	next[n][0]=-1;
	while(i<length)
	{
		if (j==-1||c[n][i]==c[n][j])
		{
			i++;
			j++;
			next[n][i]=j;
		}
		else
		{
			j=next[n][j];
		}
	}
}

int	KMP(int  n,int length)
{

	int i=0,j=0;
	int length1=strlen(substring);
	while (i<length&&j<length1)
	{
		if (j==-1||c[n][i]==substring[j])
		{
			i++;
			j++;
		}
		else
		{
			
			j=next[n][j];
		}
	}
	
	if (j>=length1)
	{
		return i-length1 ;
	}
	else
		return -3;
	
	
}
int main()
{
	int case1;
	scanf("%d",&case1);
	while (case1--)
	{
		int  num;
		scanf("%d",&num);
		int i,j;
		for(i=0;i<num;i++)
		{
			scanf("%s",c[i]);	
			int length=strlen(c[i]);
			getnext(i,length);//计算每个字符串的next
		}
		int length1=strlen(c[0]);
		int tans=0;
	
		//枚举从c[0]所有子串
		for (i=2;i<length1;i++)//i表示子串长度
		{
			for (j=0;j<length1;j++)//j   表示子串第一个元素位置
			{
				substring[0]='\0';
				strncpy(substring,c[0]+j,i+1);//得到一个子串
				int flag=1;
				int slen=strlen(substring);
				//判断子串在不在目标串中
				for (int k=1;k<num;k++)
				{
					int temp=KMP(k,strlen(c[k]));
					
					
					if (temp==-3)//说明这个子串不存在于c[k]
					{
						flag=0;
						break;
					}
				}
				if (flag==1)
				{
					if (tans==slen)
					{
						if (strcmp(cans,substring)>0)
						{
						tans=slen;

						strcpy(cans,substring);	
						}
					}
					if (tans<slen)
					{
						tans=slen;
						strcpy(cans,substring);	
					}
					
				}
			}
		}
		
		if (tans<3)
		{
			cout<<"no significant commonalities"<<endl;
		}
		else
			cout<<cans<<endl;
		
	}
	
}