(串的模式匹配4.6.1)POJ 3080 Blue Jeans(使用素朴的模式匹配算法求最长的公共子串)

(串的模式匹配4.6.1)POJ 3080 Blue Jeans(使用朴素的模式匹配算法求最长的公共子串)

/*
 * POJ_1080.cpp
 *
 *  Created on: 2013年10月25日
 *      Author: Administrator
 */

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int maxm = 15;
const int maxs = 65;

int main(){
	int t;
	scanf("%d",&t);
	while(t--){
		int m;
		int len = 0;
		char ans[maxs];

		scanf("%d",&m);
		char p[maxm][maxs];

		int i,j,k;
		for(i = 0 ; i < m ; ++i){
			scanf("%s",&p[i]);
		}

		for(i = 0 ; i < strlen(p[0]) ; ++i){
			for(j = i + 2 ; j < strlen(p[0]) ; ++j){
				char s[maxs];

				strncpy(s,p[0] + i,j - i + 1);//将p[0]+i位置以后的j - i + 1个字符复制到s中
				s[j-i+1] = '\0';//注意,因为他是字符串,所以尽量加上'\0'

				bool ok = true;
				for(k = 1 ; ok && k < m ; ++k){
					if(strstr(p[k],s) == NULL){//strstr(str1,str2) :判断str1中是否含有str2
						ok = false;
					}
				}

				if(ok&& (j - i + 1 > len || (j - i + 1 == len && strcmp(ans,s) > 0))){
					len = j - i + 1;
					strcpy(ans,s);
				}
			}
		}

		if(len < 3){
			printf("no significant commonalities\n");
		}else{
			printf("%s\n",ans);
		}
	}

	return 0;

}