题目链接: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" 是北京大学在线编程平台POJ(Problem Online Judge)上的一道算法竞赛题目。这道题目主要考察的是动态规划和数组处理的能力,是许多编程爱好者和竞赛选手在提升算法技能时会遇到的经典...
北大ACM-POJ3080 - Blue Jeans 原比赛题目的测试数据
poj 3715 Blue and Red.md
《KMP算法在POJ题目中的应用》 KMP(Knuth-Morris-Pratt)算法,是一种在字符串中寻找子串的搜索算法,由Donald Knuth、Vaughan Pratt和James H. Morris三位学者于1970年代提出。在编程竞赛如POJ(Problemset On...
* 串:例如 poj1035、poj3080、poj1936。 * 排序:例如 poj2388、poj2299。 * 简单并查集的应用。 * 哈希表和二分查找等高效查找法:例如 poj3349、poj3274、poj2151、poj1840、poj2002、poj2503。 * 哈夫曼树...
- **例题**:poj1035, poj3080, poj1936 - **解释**:树形数据结构的题目通常涉及树的遍历、查找等问题。 #### 2. 字符串 - **例题**:poj2388, poj2299 - **解释**:字符串问题通常涉及字符串的模式匹配、编辑距离...
- 字符串处理:如KMP算法和后缀数组,用于字符串搜索和模式匹配,如`poj1035, poj3080`。 - 排序算法:如快速排序和归并排序,用于对数据进行排序,如`poj2388, poj2299`。 - 并查集:用于处理集合的合并和查询...
poj的代码,KMP没什么难度算法易证。
* 串:串是指解决问题的基本数据结构,如 poj1035、poj3080、poj1936。 * 排序:排序是指解决问题的排序算法,如快排、归并排、堆排。 * 简单并查集:简单并查集是指解决问题的简单并查集算法。 * 哈希表和二分查找...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj1035、poj3080等训练了串的操作,poj2388、poj2299等则涉及排序问题,poj2524、poj1611等是并查集的实例,poj3349、poj3274等展示了哈希表和二分查找,poj3253是哈夫曼树的题目,poj2442和poj1442则关于堆。...
- (poj1035, poj3080, poj1936):基本的数据结构及其应用场景。 2. **树**: - (poj2388, poj2299):介绍二叉树、平衡二叉树等。 3. **字符串处理**: - (poj3349, poj3274, POJ2151, poj1840, poj2002, poj...
如Trie树(前缀树)、KMP算法,用于字符串匹配和索引构建,见poj2513和poj1961。 #### 排序 快速排序、归并排序和堆排序等,不仅用于排序,也常用于解决与逆序数相关的问题,如poj2388。 #### 并查集 用于处理集合...
例如,题目poj1961和poj2406就是KMP算法的应用实例。 ### 7. 几何算法 几何算法涉及点、线、面的性质和关系,如凸包、最近点对、三角剖分等问题。这些算法在计算机图形学、地理信息系统等领域有着广泛的应用。例如...
标题中的“POJ_3131.zip_POJ 八数码_poj”指的是一个与编程竞赛网站POJ(Problem Set Algorithm)相关的项目,具体是针对3131号问题的解决方案,该问题涉及到了八数码游戏。八数码游戏,又称滑动拼图,是一个经典的...
【标题】"POJ.rar_poj java_poj1048" 涉及的知识点主要围绕编程竞赛中的“约瑟夫环”问题,这里是一个加强版,使用Java语言进行解决。 【描述】"POJ1048,加强版的约瑟夫问题 难度中等" 提示我们,这个问题是编程...
【标题】"POJ1159-Palindrome" 是北京大学在线编程平台POJ上的一道编程题目。这道题目主要考察的是字符串处理和回文判断的知识点。 【描述】"北大POJ1159-Palindrome 解题报告+AC代码" 暗示了解决这道问题的方法和...
【标题】"POJ2002-Squares"是一个经典的计算机编程题目,源自北京大学的在线判题系统(POJ,即PKU Online Judge)。这个题目主要涉及到算法设计和实现,尤其是数学和动态规划方面的知识。 【描述】"解题报告+AC代码...
【标题】"POJ1837-Balance"是一个在线编程竞赛题目,源自著名的编程练习平台POJ(Programming Online Judge)。这个题目旨在测试参赛者的算法设计和实现能力,特别是处理平衡问题的技巧。 【描述】"解题报告+AC代码...
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告