hdu 2594 Simpsons’ Hidden Talents 【KMP】
HDU KMP hidden
2023-09-14 09:10:12 时间
题目链接:http://acm.acmcoder.com/showproblem.php?pid=2594
题意:求最长的串 同一时候是s1的前缀又是s2的后缀。输出子串和长度。
思路:kmp
代码:
#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char s1[500010],s2[500010];
char ANS[500010];
void get_next(char x[], int m, int Next[])
{
int i, j;
j = Next[0] = -1;
i = 0;
while (i < m)
{
while (-1 != j && x[i] != x[j]) j = Next[j];
Next[++i] = ++j;
}
}
int Next[1001000];
int KMP(char x[], int m, char y[], int n)//x模式串 y主串
{
int i, j;
i = j = 0;
get_next(x, m, Next);
if (n > m) i = n - m;
while (i < n)
{
if (j == -1 || y[i] == x[j])
{
i++;
j++;
}
else j = Next[j];
}
return j;
}
int main()
{
while (cin>>s1>>s2)
{
int len1 = strlen(s1);
int len2 = strlen(s2);
int ans = KMP(s1, len1, s2, len2);
if (ans !=0 )
{
for(int i=0;i<ans;i++) cout<<s1[i];cout<<" ";
}
cout<<ans<<endl;
}
return 0;
}
相关文章
- HDU 1556-差分数组和线段树的对比分析-Color the ball
- hdu 3980 Paint Chain(SG函数)
- HDU 3336 KMP算法中对next数组的理解「建议收藏」
- HDU P3341 Lost’s revenge 题解+数据生成器
- hdu 3336 Count the string(kmp应用)
- hdu 3336 Count the string 用心写的题解
- hdu 1142_hdu1001
- HDU 3336 Count the string 解题报告
- [ACM] HDU 1006 解题报告
- H - Partial Tree HDU - 5534 【 完全背包 】
- HDU-2084 数塔
- 敌兵布阵(HDU 1166)
- I Hate It (HDU 1754)
- 校庆神秘建筑(HDU 1411)
- 还是畅通工程(HDU 1233)
- Friend-Graph (HDU 6152)2017中国大学生程序设计竞赛 - 网络选拔赛
- CaoHaha's staff (HDU 6154)(2017中国大学生程序设计竞赛 - 网络选拔赛)
- Oil Deposits (HDU - 1241 )(DFS思路 或者 BFS思路)
- 畅通工程续(HDU 1874)(简单最短路)
- Drainage Ditches (HDU - 1532)(最大流)
- Ancient Go ( HDU - 5546 ) ( BFS 搜索是否相连)
- 统计难题 【 HDU - 1251 】【 字典树 】
- Phone List 【 HDU - 1671 】 【 字典树判断是否存在前缀 】
- A * B Problem Plus【HDU 1402】 【FFT求高精度乘法】
- Bone Collector HDU - 2602【 01 背包 】
- KMP算法在Oracle环境中的应用实践(kmp oracle实现)