程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> hdu 2203 親和串 KMP入門

hdu 2203 親和串 KMP入門

編輯:關於C++

親和串

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 ;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved