首页 > ACM题库 > HDU-杭电 > hdu 2594 Simpsons’ Hidden Talents-KMP-[解题报告]C++
2014
02-10

hdu 2594 Simpsons’ Hidden Talents-KMP-[解题报告]C++

Simpsons’ Hidden Talents

问题描述 :

Homer: Marge, I just figured out a way to discover some of the talents we weren’t aware we had.
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.

输入:

Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase.

输出:

Input consists of two lines. The first line contains s1 and the second line contains s2. You may assume all letters are in lowercase.

样例输入:

clinton
homer
riemann
marjorie

样例输出:

0
rie 3

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=50000+10;
char s1[MAX*2],s2[MAX];
int next[MAX*2];

void get_next(char *a){
	int i=-1,j=0,len=strlen(a);
	next[0]=-1;
	while(j<len){
		if(i == -1 || a[i] == a[j])next[++j]=++i;
		else i=next[i];
	}
	return;
}

int main(){
	while(cin>>s1>>s2){
		int lena=strlen(s1),lenb=strlen(s2),len=lena+lenb;
		strcat(s1,s2);
		get_next(s1);
		while(next[len]>lena || next[len]>lenb)len=next[len];
		len=next[len];
		for(int i=0;i<len;++i)cout<<s1[i];
		if(len)cout<<' ';
		cout<<len<<endl; 
	}
	return 0;
}

解题转自:http://blog.csdn.net/xingyeyongheng/article/details/9285989


,