本文主要是介绍HDU 2594 Simpsons’ Hidden Talents(s1的前缀是s2的后缀),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1、http://acm.hdu.edu.cn/showproblem.php?pid=2594
2、题目大意:
给定两个字符串s1,s2,求一个最长的子串,该字串是s1的前缀并且是s2的后缀
开始用for循环做的超时,其实直接用KMP模板即可
3、题目:
Simpsons’ Hidden Talents
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1534 Accepted Submission(s): 564
Marge: Yeah, what is it?
Homer: Take me for example. I want to find out if I have a talent in politics, OK?
Marge: OK.
Homer: So I take some politician’s name, say Clinton, and try to find the length of the longest prefix
in Clinton’s name that is a suffix in my name. That’s how close I am to being a politician like Clinton
Marge: Why on earth choose the longest prefix that is a suffix???
Homer: Well, our talents are deeply hidden within ourselves, Marge.
Marge: So how close are you?
Homer: 0!
Marge: I’m not surprised.
Homer: But you know, you must have some real math talent hidden deep in you.
Marge: How come?
Homer: Riemann and Marjorie gives 3!!!
Marge: Who the heck is Riemann?
Homer: Never mind.
Write a program that, when given strings s1 and s2, finds the longest prefix of s1 that is a suffix of s2.
The lengths of s1 and s2 will be at most 50000.
clinton homer riemann marjorie
0 rie 3
4、代码:
#include<stdio.h>
#include<string.h>
#define N 50005
char s1[N];
char s2[N];
int f[N];
void getFail(char *p, int *f)
{
int m=strlen(p);
f[0]=f[1]=0;
for(int i=1; i<m; ++i)
{
int j=f[i];
while(j && p[i]!=p[j])j=f[j];
f[i+1] = p[i]==p[j]?1+j:0;
}
}
int find(char *T,char *p,int *f)//传入的三个参数分别是主字符串,要比较的子模板串,子模板串的模式值数组
{
getFail(p,f);
int n=strlen(T);
int m=strlen(p);
int j=0;
for(int i=0; i<n; ++i)//循环主串中的字符
{
//如果出现字符不匹配,没必要从头循环,只需要从模式值f[j]查找
while(j && T[i]!=p[j])j=f[j];//可以保证循环到最后,即保证是后缀
if(T[i]==p[j])++j;
}
return j;
}
int main()
{
while(scanf("%s%s",s1,s2)!=EOF)
{
int id=find(s2,s1,f);
if(id==0)
printf("0\n");
else
{
for(int i=0;i<id;i++)
printf("%c",s1[i]);
printf(" %d\n",id);
}
}
return 0;
}
/*
clinton
homer
riemann
marjorie
riem
riemori
*/
这篇关于HDU 2594 Simpsons’ Hidden Talents(s1的前缀是s2的后缀)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!