hdu 2203 親和串 KMP入門

親和串

Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9065 Accepted Submission(s): 4135


Problem Description 人隨著歲數的增長是越大越聰明還是越大越笨，這是一個值得全世界科學家思考的問題,同樣的問題Eddy也一直在思考，因為他在很小的時候就知道親和串如何判斷了，但是發現，現在長大了卻不知道怎麼去判斷親和串了，於是他只好又再一次來請教聰明且樂於助人的你來解決這個問題。
親和串的定義是這樣的：給定兩個字符串s1和s2,如果能通過s1循環移位，使s2包含在s1中，那麼我們就說s2 是s1的親和串。

Input 本題有多組測試數據，每組數據的第一行包含輸入字符串s1,第二行包含輸入字符串s2，s1與s2的長度均小於100000。

Output 如果s2是s1的親和串，則輸出yes，反之，輸出no。每組測試的輸出占一行。

Sample Input

AABCD
CDAA
ASD
ASDF

Sample Output

yes
no

先說下解題思路，其實我們只要s1字符 串依次復制兩次就可以了，因為無論怎麼移位，也不可能超過兩倍於s1的長度，比如說asdfg字符串，我們只要把他這樣保存在s3中就可以了，，s3=asdfgasdfg.
有兩種代碼，一種是KMP，，，還有就是利用C語言庫函數裡的strstr()函數 KMP代碼：

#include 
#include 
#define MAX 100100
char str1[MAX] , str2[MAX] , str3[MAX*2];
int next[MAX] ;
void getNext()
{
	int i = -1 , j = 0 ;
	int len = strlen(str2) ;
	next[0] = -1 ;
	while(j

不用KMP代碼：
#include 
#include 
#define MAX 100100
char str1[MAX] , str2[MAX] , str3[MAX*2];
int main()
{
	while(gets(str1))
	{
		gets(str2) ;
		strcpy(str3,str1) ;
		strcpy(str3+strlen(str1),str1) ;
		if(strstr(str3,str2))
			puts(yes) ;
		else
			puts(no) ;
	}
	return 0 ;
}