【算法】模式匹配之KMP

字符串匹配，是指模式串是否为主串的子串。朴素的匹配算法是一种brute-force：从串的第一个字符开始匹配；当匹配失败时，主串S从第二个字符、模式串P继续从第一个字符开始匹配，…，直至匹配成功或比较到S串的最后一个字符。显然，这种算法的复杂度较高为O(m*n)，且S串、P串的长度分别为m、n。

鉴于此，Knuth、Pratt和Morris提出了一种高效的匹配算法，复杂度仅为O(m&＃43;n)。利用到了模式串的字符信息与匹配失败的位置，以确定下一步比较的主串。先定义：

失配函数有快速计算方法，可用如下等价公式进行计算

[1] Horowitz ..., 《数据结构基础》, 清华出版社.

[2] A_B_C_ABC, KMP字符串模式匹配详解.

[3] 模式匹配的一种改进算法----KMP算法.

[4]
KMP visulization.

3.1 POJ 3461

求模式串在母串中出现的次数

主串数组开小了，Runtime Error。

源代码：

#include "stdio.h"
#include "string.h"
#define MAXW 10000
#define MAXT 1000000
char string[MAXT],pat[MAXW];
int failure[MAXW];
int kmp(char *string, char *pat)
{
int i=0,j=0,count=0;
int lens=strlen(string),lenp=strlen(pat);
while(i {
if(string[i]==pat[j])
{
i++;j++;
}
else if(j==0) i++;
else j=failure[j-1]+1;
if(j==lenp) //matched
count++;
}
return count;
}
void compute_failure(char *pat)
{
int i,j;
int lenp=strlen(pat);
failure[0]=-1;
for(j=1;j {
i=failure[j-1];
while((pat[j]!=pat[i+1])&&i>=0)
i=failure[i];
if(pat[j]==pat[i+1])
failure[j]=i+1;
else failure[j]=-1;
}
}
int main()
{
int test_cases;
scanf("%d",&test_cases);
while(test_cases--)
{
scanf("%s%s",&pat,&string);
compute_failure(pat);
printf("%d\n",kmp(string,pat));
}
return 0;
}

【算法】模式匹配之KMP,布布扣,bubuko.com