POJ-3080 Blue Jeans(kmp+暴力求子串)

题目

---

题意：

给一个n，输入n个长度为60的字符串，求==最长公共子串==（2<n<=10),如果公共串长度大于等于3就输出这个子串（~~开始真的是瞎了，看了题直接将所有字符串连接来，求了波next数组，然后完美求出了子串长度，却发现要求是输出子串，心里***~~）**

---

思路：

(==KMP+暴力求子串==)枚举第一个字符串的不同长度子串，判断她是否为下面多有的公共子串？如果是的话，那么我们就表明找到，则比较其长度，如果比已经找到的串长，那么就替换结果串 否则按字典序比较。取字典序考前的，就可以。

---

代码：

#include<cstdio>
#include<bits/stdc++.h>
using namespace std;
char str[10][62];
char substr[62];
char result[62];
char temp[62];
int next[62];
int len, n, max;
void get_next() {
	next[0] = -1;
	int j = -1;
	for (int i = 1; i < len; i++) {
		while (j > -1 && substr[j + 1] != substr[i])
			j = next[j];
		if (substr[j + 1] == substr[i])  j++;
		next[i] = j;
	}
}
void kmp() {
	int j, m;
	get_next();
	for (int k = 1; k < n; k++) {
		j = -1, m = -1;//m最好取-1
		for (int i = 0; i < 60; i++) {
			while (j > -1 && substr[j + 1] != str[k][i])
				j = next[j];
			if (substr[j + 1] == str[k][i]) j++;
			if (j > m) m = j; //m取可匹配到的最大值
		}
		if (m < max)   max = m;//max取可匹配到的最小值，公共子串以最小者为准
	}
}
int main() {
	int t, i, ans;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		for (i = 0; i < n; i++)
			scanf("%s", str[i]);
		ans = 0;
		for (i = 0; i < 58; i++) {
			strcpy(substr, str[0] + i);//枚举第一个串的所有后缀串
			len = 60 - i;
			max = 65;
			kmp();
			if (max > ans) {
				ans = max;
				strncpy(result, str[0] + i, ans + 1);
				result[ans + 1] = '\0';
			}
			else if (max == ans) { //若有相等长度，取字典序小者
				strncpy(temp, str[0] + i, ans + 1);
				temp[ans + 1] = '\0';
				if (strcmp(result, temp) > 0)
					strcpy(result, temp);
			}
		}
		if (ans >= 2)
			printf("%s\n", result);
		else
			printf("no significant commonalities\n");
	}
	return 0;
}