题目链接:hdu 2328 Corporate Identity
题目大意:给出若干个串,求最长公共子串。
解题思路:和poj 3080一样的做法。
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 4005;
const int M = 205;
int n, m, len, jump[M];
char s[N][M], str[M];
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) {
for (int i = 0; i < ans; i++)
printf("%c", s[0][i+rec]);
printf("\n");
} else {
printf("IDENTITY LOST\n");
}
}
int main () {
while (scanf("%d", &n) == 1 && n) {
for (int i = 0; i < n; i++)
scanf("%s", s[i]+1);
solve ();
}
return 0;
}
分享到:
相关推荐
4. **字符串处理**:KMP算法、Manacher's Algorithm、Rabin-Karp算法等。 5. **数学应用**:组合数学、数论(质因数分解、模运算、欧几里得算法等)、概率论等。 6. **编码技巧**:IO优化(如scanf/printf代替cin/...
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
【标题】"HDU_2010.rar"是一个压缩包文件,其中包含了与"HDU 2010"相关的资源,特别是针对"HDU ACM20"比赛的编程题目。"hdu 2010"和"hdu 20"可能是该比赛的不同简称或分类,而"hdu acm20"可能指的是该赛事的第20届...
ACM HDU 题目分类 ACM HDU 题目分类是指对 HDU 在线判题系统中题目的分类,总结了大约十来个分类。这些分类将有助于编程选手更好地理解和解决问题。 DP 问题 DP(Dynamic Programming,动态规划)是一种非常重要...
### hdu1250高精度加法 #### 背景介绍 在计算机科学与编程竞赛中,处理大整数运算(特别是加法、减法、乘法等)是常见的需求之一。当数字的位数超过了标准数据类型(如`int`、`long`等)所能表示的最大值时,就需要...
【ACM HDU】指的是在ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest)中,参赛者在杭州电子科技大学(Hangzhou Dianzi University,简称HDU)的在线评测系统上完成并已解决的题目集合...
【标题】"HDU DP动态规划"涉及到的是在算法领域中的动态规划(Dynamic Programming,简称DP)技术,这是解决复杂问题的一种高效方法,尤其适用于有重叠子问题和最优子结构的问题。动态规划通常用于优化多阶段决策...
3. **字符串处理**:杭电ACM中的题目可能涉及到字符串匹配(KMP算法、Boyer-Moore算法)、编码解码、模式查找等问题,熟悉字符串操作是必备技能。 4. **数学应用**:很多ACM题目需要应用到基础数学知识,例如数论...
HDU是杭州电子科技大学(Hangzhou Dianzi University)举办的一个在线编程竞赛平台,全称为HDU Online Judge。ACM是国际大学生程序设计竞赛(International Collegiate Programming Contest)的缩写,是一个全球性的...
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
3. **字符串处理**:KMP、Boyer-Moore、Rabin-Karp等字符串匹配算法,以及字符串操作和模式匹配技巧。 4. **数学知识**:组合数学、离散数学、数论等,许多竞赛题目需要运用到这些数学原理。 5. **优化技巧**:...
【标题】"HDU题目java实现"所涉及的知识点主要集中在使用Java编程语言解决杭州电子科技大学(HDU)在线评测系统中的算法问题。HDU是一个知名的在线编程竞赛平台,它提供了大量的算法题目供参赛者练习和提交解决方案...
hdu2101AC代码
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
"yfndq2"可能是一个字符串处理或模式匹配的问题,可能用到了KMP、Boyer-Moore等字符串匹配算法。而"flymaidou"可能是涉及数值计算或数学推理的题目,需要理解和应用特定的数学公式或方法。 在学习这些源代码时,...
【ACM入门与提高:HDU ACM竞赛课程详解】 ACM(国际大学生程序设计竞赛,International Collegiate Programming Contest,简称ICPC或ACM/ICPC)是一项全球性的竞赛,旨在激发大学生对计算机科学的兴趣,提升他们的...
hdu 1166线段树代码
【标题】"HDU.rar_hdu_hdu07_com_shownv9b_www.563hdu." 暗示这是一个与HDU(杭州电子科技大学在线编程平台)相关的压缩包,其中可能包含了该平台上的编程竞赛题目或练习题目的源代码。"hdu07"可能是某个特定题目的...