首页 > 代码库 > 字符串匹配算法之KMP

字符串匹配算法之KMP

KMP是单模匹配算法,主串是S,模式串是P,查找P在S中出现的位置。

主要是思想是主串的索引 i 递增,当主串与模式串发生不匹配时,把模式串右移,右移的位数为 j – fail[j] ,对于模式串计算fail函数,这个函数用来表示计算模式串某个位置发生失配时,模式串重新匹配的位置。

image

fail应该指向最后一个可能产生匹配的地方,P[1..fail[j]-1]是P[1..j-1]的最长相等前缀后缀。

image

有个优化的地方:如果P[j]和P[fail[j]]是同一个字符,那么回溯后马上又匹配失败,可以直接令fail[j] = fail[fail[j]]。

c++代码示例:

计算fail函数代码:

#include<iostream>using namespace std;// kmp fail arrayvoid computefailure(int fail[],int n,char p[]){    int j = 0;    for(int i = 1;i<=n;i++){        if(p[i] == p[j])            fail[i] = fail[j];        else            fail[i] = j;        while(j>0 && p[i]!=p[j])            j = fail[j];        j = j+1;    }}int main(){    char p[] = { ,A,B,B,A,B,B,A,B,A,B,B};    int fail[20];    int len = 11;    computefailure(fail,len,p);    for(int i=1;i<=len;i++)        cout<<fail[i]<<endl;    return 0;}

 

KMP算法示例:

#include<iostream>using namespace std;const int MAX_N = 100;int fail[MAX_N];// kmp fail arrayvoid computefailure(int fail[],int n,char p[]){    int j = 0;    for(int i = 1 ; i <= n ; i++){        if( p[i] == p[j] )            fail[i] = fail[j];        else            fail[i] = j;        while( j>0 && p[i]!=p[j] )            j = fail[j];        j = j+1;    }}int kmp(char T[],int n,char P[],int m){    int j = 1;    for (int i = 1; i <= n ; i++){        while( j>0 && T[i] != P[j])            j = fail[j];        if( j == m )            return i-m+1;        j = j+1;    }    return -1;}int main(){    char T[] = { ,A,B,B,A,B,B,A,B,A,B,B};    char P[] = { ,B,B,A};    int lenT = 11;    int lenP = 3;    computefailure(fail,lenP,P);    cout<<kmp(T,lenT,P,lenP)<<endl;    return 0;}