首页 > 代码库 > hdu2203 KMP水题
hdu2203 KMP水题
两种方法 第一种是纯粹KMP
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
char str1[200010],str2[100010];
int next[100010];
int get()
{
next[0]=-1;
int j=0;
int k=-1;
int len=strlen(str2);
while(j<len-1)
{
if(k==-1||str2[k]==str2[j])
{
j++;
k++;
next[j]=k;
}
else k=next[k];
}
return 0;
}
int main()
{
int i,j;
while(~scanf("%s%s",str1,str2))
{
get();
char str[100010];
strcpy(str,str1);
strcat(str1,str);
//printf("&&&&\n");
int len1=strlen(str1);
int len2=strlen(str2);
int i=j=0;
while(i<len1&&j<len2)
{
if(j==-1||str1[i]==str2[j])
{
i++;
j++;
}
else j=next[j];
}
if(j==len2) printf("yes\n");
else printf("no\n");
}
return 0;
}
下面是用了STL里面的函数
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int main()
{
char str1[200010],str2[100010],str[100010];
int i,j;
while(~scanf("%s%s",str1,str2))
{
strcpy(str,str1);
strcat(str1,str);
if(strstr(str1,str2)) printf("yes\n");
else printf("no\n");
}
return 0;
}
hdu2203 KMP水题