题目链接:poj 3080 Blue Jeans
题目大意:给出若干个串,求出这若干个串的最长公共子串。
解题思路:枚举第一个串的起始,作为匹配串,和剩下的所有串进行KMP维护最长的公共串。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 105;
const int M = 15;
int n, m, len, jump[N];
char s[M][N], str[N];
void init () {
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%s", s[i]+1);
}
void getJump () {
int p = 0;
for (int i = 2; i <= m; i++) {
while (p > 0 && str[p+1] != str[i])
p = jump[p];
if (str[p+1] == str[i])
p++;
jump[i] = p;
}
}
int KMP (int j) {
int ans = 0, p = 0;
for (int i = 1; i <= len; i++) {
while (p > 0 && str[p+1] != s[j][i])
p = jump[p];
if (str[p+1] == s[j][i])
p++;
ans = max(p, ans);
if (p == m) break;
}
return ans;
}
bool judge (int p, int q, int k) {
for (int i = 0; i < k; i++) {
if (s[0][p+i] != s[0][q+i])
return s[0][p+i] < s[0][q+i];
}
return true;
}
void solve () {
int ans = 0, rec = 0;
len = strlen(s[0]+1);;
for (int i = 1; i < len; i++) {
strcpy (str+1, s[0]+i);
m = strlen (str+1);
getJump ();
int tmp = len;
for (int j = 1; j < n; j++)
tmp = min(tmp, KMP(j));
if (tmp > ans || (tmp == ans && judge (i, rec, ans))) {
ans = tmp;
rec = i;
}
}
if (ans > 1) {
for (int i = 0; i < ans; i++)
printf("%c", s[0][i+rec]);
printf("\n");
} else {
printf("no significant commonalities\n");
}
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init ();
solve ();
}
return 0;
}
分享到:
相关推荐
北大POJ3080-Blue Jeans 解题报告+AC代码
北大ACM-POJ3080 - Blue Jeans 原比赛题目的测试数据
poj 3715 Blue and Red.md
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
poj的代码,KMP没什么难度算法易证。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类