首页 > 代码库 > KMP字符串模式匹配算法（C++实现）

KMP字符串模式匹配算法（C++实现）

2024-09-02 05:46:05   218人阅读

鉴于原理有点复杂，详细原理可以参考这篇文章http://blog.csdn.net/v_july_v/article/details/7041827

　　本文直接从结论入手，应付考试和竞赛足够了。

　　设T为目标串（"aaabbbaabbabcabcabbaba"），pat为模式串（"aabbabc"）。

　　这是模式串的next数组：

j(下标) 0 1 2 3 4 5 6
pat a a b b a b c
next[j] -1 0 1 0 0 1 0

　　KMP算法：

　　j=0时，next[j]=-1。表示下一趟匹配比较时，模式串的第-1个字符与目标串上次失配的位置对齐。（其实等同于第0个字符与目标串上次失配的下一个位置对齐），模式串需要移动到posT-next[j]的位置。（posT为T串下标）

　　j=1时，next[j]=0。表示下一趟匹配比较时，模式串的第0个字符与目标串上次失配的位置对齐。模式串需要移动到posT-next[j]个位置。

　　j=2时，next[j]=1。表示下一趟匹配比较时，模式串的第1个字符与目标串上次失配的位置对齐。模式串需要移动到posT-next[j]个位置。

　　以此类推......

　　

　　那么下面只要求出next数组即可，next数组是如何形成的？

　　从下标0开始，一直到lengthP-1为止（lengthP是模式串的长度），每次寻找该下标前面前缀与后缀相同的最大长度（前后缀不包括前面整个字符串，即起始位置和终止位置都相等的那一个字符串，下面有解释）。

　　j=0时，字符a前面无字符，故标记-1；

　　j=1时，字符a前面有字符a，但由于“前后缀不包括前面整个字符串”的规则，所以并没有相同的前后缀一说，故标记为0。

　　j=2时，字符b前面有字符aa，前后缀相同的字符串为a，故标记为前后缀的长度1。

　　以此类推......(PS：前后缀的计算都是从左到右的)

　　其实这样说是为了方便理解next数组，而next数组的实际形成也是一次KMP算法，它也是一个匹配字符串的过程，用后缀去匹配前缀的过程。

　　代码如下：

　　

 1 #include<iostream>
 2 #include<string>
 3 using namespace std;
 4 string T;
 5 string pat;
 6 void getNext(int next[],int lengthP){//lengthP为模式串P的长度 
 7     int j=0,k=-1;//j为P串的下标，k用来记录该下标对应的next数组的值 
 8     next[0]=-1;//初始化0下标下的next数组值为-1 
 9     while(j<lengthP){ //对模式串进行扫描 
10         if(k==-1||pat[j]==pat[k]){//串后缀与前缀没有相等的子串或者此时j下标下的字符与k下的字符相等。 
11             j++;k++; 
12             next[j]=k;//设置next数组j下标的值为k 
13         }else
14             k=next[k];//缩小子串的范围继续比较 
15     }
16 }
17 
18 int kmp(int k,int next[]){
19     int posP=0,posT=k;//posP和posT分别是模式串pat和目标串T的下标，先初始化它们的起始位置 
20     int lengthP=pat.length();//lengthP是模式串pat长 
21     int lengthT=T.length();//lengthT是目标串T长 
22     while(posP<lengthP&&posT<lengthT){//对两串扫描 
23         if(posP==-1||pat[posP]==T[posT]){//对应字符匹配 
24             posP++;posT++;
25         }else
26             posP=next[posP];//失配时，用next数组值选择下一次匹配的位置 
27     }
28     if(posP<lengthP) return -1;
29     else return posT-lengthP;//匹配成功 
30 }
31 
32 int main(){
33     T="aaabbbaabbabcabcabbaba";
34     pat="aabbabc";
35     int lengthP=pat.length();
36     int next[lengthP]={0};
37     getNext(next,lengthP);
38     int pos=kmp(0,next);
39     cout<<pos<<endl;
40     cout<<"next[]:";
41     for(int i=0;i<lengthP;i++){
42         cout<<next[i]<<" "; 
43     } 
44     return 0;
45 }

　　

　　

　　

　　

　　

KMP字符串模式匹配算法（C++实现）


联系
我们