首页 > 代码库 > 字符串匹配算法之KMP
字符串匹配算法之KMP
KMP是单模匹配算法,主串是S,模式串是P,查找P在S中出现的位置。
主要是思想是主串的索引 i 递增,当主串与模式串发生不匹配时,把模式串右移,右移的位数为 j – fail[j] ,对于模式串计算fail函数,这个函数用来表示计算模式串某个位置发生失配时,模式串重新匹配的位置。
fail应该指向最后一个可能产生匹配的地方,P[1..fail[j]-1]是P[1..j-1]的最长相等前缀后缀。
有个优化的地方:如果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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。