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

字符串匹配算法之KMP

2024-07-18 22:21:51   229人阅读

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;}


联系
我们