NYOJ 5 Binary String Matching （kmp 字符串匹配）

Binary String Matching

时间限制：3000ms | 内存限制：65535KB

难度：3

描述

Given two strings A and B, whose alphabet consist only ‘0’ and ‘1’. Your task is only to tell how many times does A appear as a substring of B? For example, the text string B is ‘1001110110’ while the pattern string A is ‘11’, you should output 3, because the pattern A appeared at the posit

输入

The first line consist only one integer N, indicates N cases follows. In each case, there are two lines, the first line gives the string A, length (A) <= 10, and the second line gives the string B, length (B) <= 1000. And it is guaranteed that B is always longer than A.

输出

For each case, output a single line consist a single integer, tells how many times do B appears as a substring of A.

样例输入

3
11
1001110110
101
110010010010001
1010
110100010101011 

样例输出

3
0
3 

来源

网络

上传者

naonao

南阳oj上这道题太水了；直接用朴素算法暴力就水过了，数据量太少了，然后我们把题目移到我们自己的oj上，自己多出了一些数据，测试了一下，朴素算法用时3300ms，kmp用时1700ms左右，仅供参考，足以显示出kmp算法的优越性啊，最近两天也看了好久kmp，感觉有些细节的地方还是理解的不到位；还是要多回顾理解，看的是july大神的博客kmp算法讲的比较详细，多读几遍，大话数据结构上分析的也比较好；供自己以后复习回顾；

下面是朴素算法过的，暴力；

朴素算法关键在于回溯，处理好回溯；

#include<cstdio>
#include<cstring>
intmain()
{
intn,count;
chara[200],b[1200];
scanf("%d",&n);
getchar();
while(n--)
{
count=0;
inti=0,j=0,len;
scanf("%s\n%s",a,b);
len=strlen(b);
while(i<=len)
{
if(a[j]=='\0')
{
count++;
i=i-j+1;
j=0;
}
elseif(a[j]==b[i])
{
i++;
j++;
}
else
{
i=i-j+1;//关键在于回溯
j=0;
}
}
printf("%d\n",count);
}
return0;
}

下面是kmp算法，还要多多加强，巩固理解；

朴素算法中的回溯很多是不必要的，所以就有了kmp算法，用一个next数组储存下一次要匹配的位置，这里难理解的就是next数组，其中还要理解后缀和前缀的关系，通过匹配字符串前后的联系，得出next数组；而就不需要移动主串的位置；节约了回溯的时间；

#include<cstdio>
#include<cstring>
intnextval[200];
voidget_next(chara[])//得到next数组；
{
intlen;
inti=0,j=-1;
nextval[0]=-1;
len=strlen(a);
while(i<=len)
{
if(j==-1||a[i]==a[j])
{
++i;
++j;
if(a[i]==a[j])
nextval[i]=nextval[j];//把回溯的内容全换成是next数组；
else
nextval[i]=j;
}
else
j=nextval[j];
}
}
intkmp(chara[],charb[])//kmp的主体函数
{
inti=0,j=0,count=0;
intlena,lenb;
lena=strlen(a);
lenb=strlen(b);
get_next(a);
while(i<=lenb)
{
if(j==-1||a[j]==b[i])
{
++i;
++j;
}
else
j=nextval[j];
if(j>=lena)
{
count++;
j=nextval[j];
}
}
returncount;
}
intmain()
{
intn;
chara[20],b[1200];
scanf("%d",&n);
while(n--)
{
scanf("%s\n%s",a,b);
printf("%d\n",kmp(a,b));
}
return0;
}