首页 > 代码库 > 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水题