【C++】KMP算法详解

0x55AA

KMP算法简介：
    KMP算法是一种高效的字符串匹配算法，关于字符串匹配最简单的就是BF算法。BF算法是用两个游标分别指向母串S，模式串T，从开头向后面依次比较字符是否相等，如果相等继续同时向后滑动两个游标，不相等的话，T的游标回溯至开头，S的游标回溯至起初游标的下一位，这种算法原理非常简单，小学生都可以想的到。
    KMP算法是在BF算法的基础上加以改进的，它的特点是在遇到字符不匹配时候维持母串T的游标不动，而把模式串向右移动，具体移动到哪一个元素下标，这就是算法的核心思想之处了。
    假如母串的i处和模式串的j处不匹配，那么就令k=next（j），表示的意思就是：模式串在j处出现不匹配现象，此时应该将模式串向后一定到下标为k的游标处，在此与之前不匹配的元素进行比较。
Kmp算法的本质：
    如图所示：

在下标j处出现不匹配，则k = next（j），表示此时应该把下标k移动到原本j对应的位置处，用T[k]跟s[i ]进行对比。如果满足这样的条件，则有T[0],T[1],…T[k-1] = S[i-k],S[i-k+1],…S[i-1]
又因为j之前的字符串跟S都匹配，所以又有T[j-k],T[j-k+1],…T[j-1] = S[i-k],S[i-k+1],…S[i-1].所以得出  T[0],T[1],…T[k-1] = T[j-k],T[j-k+1],…T[j-1]。也就是说图中被标记出来前后两个区域的字符串相等，KMP算法的本质就是找出最大的这样一个k值满足T[0],T[1],…T[k-1] = T[j-k],T[j-k+1],…T[j-1]。
K值的求取方法：
K值的求取用到了数学中的递推的思想，求取K值只跟模式串T自身有关，跟母串S半毛钱关系都没有。先假设已经有 next(j) = k,接下来我们就去求next（j+1）的值。这个要分情况讨论:
如果T[k] = T[j]那么就很容易得到 next(j+1) = k+1 = next(j) + 1;
如果T[k] != T[j]，那么此时可以将T[0],T[1],…T[k-1],T[k]看做一个模式串，T[j-k],T[j-k+1],…T[j-1],T[j]看做一个母串，此时模式串在k处出现不匹配现象，那么我们获取next（k）= k1的值，判断T[k1]跟T[j]的值是否相等，如果相等那么next(j+1) = k1+1;如果不相等再往下求新的kn的值，直到T[kn] = T[j]，或者遍历到了模式串的开头都不想的话，此时就要把i向后移动一个位置，同时用模式串的开头指向i，或者抽象一点就是把模式串开头的前一位下标（-1）指向i。因为下标（-1）是没有意义的，所以此时等效于下标（0）指向母串的i+1。
算法的实现：
这里一共列出了三个版本的kmp算法，其中第一个是本人根据对算法的理解写的，也是最丑的一个，剩下的两个是改编严蔚敏版的《数据结构与算法》一书中的。
Algorithms.h

1. //Algorithms.h
   
2. #pragma once
   
3. #include <string>
   
4. using namespace std;
   
5. class Algorithms
   
6. {
   
7. public:
   
8.         Algorithms(void);
   
9.         static int kmp1(string str1,string str2);
   
10.         static int kmp2(string str1,string str2);
    
11.         static int kmp3(string str1,string str2);
    
12.         ~Algorithms(void);
    
13. };
    
14. 
    
15. //Algorithms.cpp
    
16. #include "Algorithms.h"
    
17. #include <vector>
    
18. #include <iostream>
    
19. using namespace std;
    
20. 
    
21. Algorithms::Algorithms(void)
    
22. {
    
23. }
    
24. Algorithms::~Algorithms(void)
    
25. {
    
26. }
    
27. 
    
28. int Algorithms::kmp1(string strS,string strT)
    
29. {
    
30.         int nSize = strT.size();
    
31.         vector<int> vecNext(nSize,-1);
    
32.         if (nSize >= 2)
    
33.                 vecNext[1] =0;
    
34.         for (int i=2;i<nSize;i++)
    
35.         {
    
36.                 int k = vecNext[i-1];
    
37.                 while (k>=0 && strT[k] != strT[i-1] )
    
38.                         k = vecNext[k];
    
39.                 if(k>=0 && strT[i-1] == strT[k])
    
40.                         vecNext[i ] = k + 1;
    
41.                 else
    
42.                         vecNext[i ] = 0;
    
43.         }
    
44.         for(int i=0;i<nSize;i++)
    
45.                 cout<<"the vector is:"<<i<<": "<<vecNext[i ]<<endl;
    
46. 
    
47.         int nLength = strS.size();
    
48.         int nCount = 0;
    
49.         int nPoss = 0;
    
50.         int nPost = 0;
    
51.        
    
52.         while(nPoss < nLength)
    
53.         {
    
54.                 if ( strS[nPoss] == strT[nPost] )
    
55.                 {
    
56.                         nPoss++;
    
57.                         nPost++;
    
58.                 }
    
59.                 else
    
60.                 {
    
61.                         nPost = vecNext[nPost];
    
62.                         if (nPost == -1)
    
63.                         {
    
64.                                 nPoss++;
    
65.                                 nPost++;
    
66.                         }
    
67.                 }
    
68. 
    
69.                 if (nPost == nSize )
    
70.                 {
    
71.                         nCount++;
    
72.                         nPost = 0;
    
73.                 }
    
74.         }
    
75.         return nCount;
    
76. }
    
77. 
    
78. int Algorithms::kmp2(string strS,string strT)
    
79. {
    
80.         int nSize = strT.size();
    
81.         vector<int> vecNext(nSize);
    
82.         int i = 0;
    
83.         vecNext[0] = -1;
    
84.         int j = -1;
    
85.         while(i<nSize-1)
    
86.         {
    
87.                 if (j==-1 || strT[i ]==strT[j])
    
88.                 {
    
89.                         i++;
    
90.                         j++;
    
91.                         vecNext[i ] = j;
    
92.                 }
    
93.                 else
    
94.                         j = vecNext[j];
    
95.         }
    
96.         for(int i=0;i<nSize;i++)
    
97.                 cout<<"the vector is:"<<i<<": "<<vecNext[i ]<<endl;
    
98. 
    
99.         int nLength = strS.size();
    
100.         int nCount = 0;
     
101.         int nPoss = 0;
     
102.         int nPost = 0;
     
103.        
     
104.         while(nPoss < nLength)
     
105.         {
     
106.                 if ( strS[nPoss] == strT[nPost] )
     
107.                 {
     
108.                         nPoss++;
     
109.                         nPost++;
     
110.                 }
     
111.                 else
     
112.                 {
     
113.                         nPost = vecNext[nPost];
     
114.                         if (nPost == -1)
     
115.                         {
     
116.                                 nPoss++;
     
117.                                 nPost++;
     
118.                         }
     
119.                 }
     
120. 
     
121.                 if (nPost == nSize )
     
122.                 {
     
123.                         nCount++;
     
124.                         nPost = 0;
     
125.                 }
     
126.         }
     
127.         return nCount;
     
128. }
     
129. 
     
130. int Algorithms::kmp3(string strS,string strT)
     
131. {
     
132.         int nSize = strT.size();
     
133.         vector<int> vecNext(nSize);
     
134.         int i = 0;
     
135.         vecNext[0] = -1;
     
136.         int j = -1;
     
137.         while(i<nSize-1)
     
138.         {
     
139.                 if (j==-1 || strT[i ]==strT[j])
     
140.                 {
     
141.                         i++;
     
142.                         j++;
     
143.                         if (strT[i ] == strT[j])
     
144.                                 vecNext[i ] =vecNext[j];
     
145.                         else
     
146.                                 vecNext[i ] = j;
     
147.                 }
     
148.                 else
     
149.                         j = vecNext[j];
     
150.         }
     
151.         for(int i=0;i<nSize;i++)
     
152.                 cout<<"the vector is:"<<i<<": "<<vecNext[i ]<<endl;
     
153. 
     
154.         int nLength = strS.size();
     
155.         int nCount = 0;
     
156.         int nPoss = 0;
     
157.         int nPost = 0;
     
158.        
     
159.         while(nPoss < nLength)
     
160.         {
     
161.                 if ( strS[nPoss] == strT[nPost] )
     
162.                 {
     
163.                         nPoss++;
     
164.                         nPost++;
     
165.                 }
     
166.                 else
     
167.                 {
     
168.                         nPost = vecNext[nPost];
     
169.                         if (nPost == -1)
     
170.                         {
     
171.                                 nPoss++;
     
172.                                 nPost++;
     
173.                         }
     
174.                 }
     
175. 
     
176.                 if (nPost == nSize )
     
177.                 {
     
178.                         nCount++;
     
179.                         nPost = 0;
     
180.                 }
     
181.         }
     
182.         return nCount;
     
183. }

复制代码

main.cpp

1. //main.cpp
   
2. #include <iostream>
   
3. #include <string>
   
4. #include <vector>
   
5. #include "Algorithms.h"
   
6. using namespace std;
   
7. 
   
8. void main()
   
9. {
   
10.         string str1,str2;
    
11.         cout<<"please input str1:"<<endl;
    
12.         cin>>str1;
    
13.         cout<<"please input str2:"<<endl;
    
14.         cin>>str2;
    
15.         //cout<<"the number of substr in str1 is:"<<Algorithms::kmp1(str1,str2)<<endl;
    
16.         //cout<<"the number of substr in str1 is:"<<Algorithms::kmp2(str1,str2)<<endl;
    
17.         cout<<"the number of substr in str1 is:"<<Algorithms::kmp3(str1,str2)<<endl;
    
18.         system("pause");
    
19. }

复制代码

算法评析：
1：Kmp1
        先说下我自己写的吧，代码没有书上的简洁，再说说几个为什么。为什么循环要从i=2开始？
因为要用到int k = vecNext[i-1]，以及strT[k] != strT[i-1]，如果从i=1开始的话，k的起始值=-1，这样就会出现越界的情况，所以就从i=2开始；另外
next（0）=-1，next（1）=0，这都是毫无疑问的东西，所以可以在前两者已知的情况下，向后求解。
2：Kmp2
        Kmp2的巧妙之处在于用了while循环，在需要i变化时才变化，否则已知变换j的值（j表示的是next（i））
3：Kmp3
        Kmp3是对kmp2的改进，它考虑到了这样的一种情况：首先在T(i) = T(j)的情况下，如果按照kmp2那么next（i+1）= j+1。但是如果T（i+1）=T(j+1)的话，那么此时就无需在拿T(j+1) 跟母串的比较，因为T(i+1)已经比较过了，并且他们不相等，所以不需要再比较T(j+1)只需要令：                                next（i+1） = next（j+1）。
按照kmp2其实是这样的：        next（i+1） = j+1，j+1 = next（j+1），
所以中间省略的一步就是：next（i+1）= j+1。
总结：
关于kmp网上的讲解很多，但是坑爹的错误程序也不少，在验证一个kmp算法程序是否坑爹，只需要把next数组的内容打印出来，将它和自己口算得到的结果比对。百度百科的C++实现的kmp算法就是错误的，坑爹的。