KMP算法——C++优化实现

C++实现Kmp字符匹配算法的优化版

 

头文件:KmpAlgorithm.h

[cpp]  view plain copy

1. #ifndef KMPALGORITHM_H  
2. #define KMPALGORITHM_H  
3. #include <string>  
4. #include <iostream>  
5. class KmpAlgorithm{  
6.     std::string s; //主串  
7.     std::string t; //子串  
8.     static const int MaxSize = 255;  
9.     int next[MaxSize];  
10.     void Get_Next(); //T串的模式匹配函数  
11. public:  
12.     KmpAlgorithm(){  
13.         std::memset(next,0,sizeof(int) * 255);  
14.         printf("请输入要匹配的字符串的主串:\n");  
15.         std::cin >> s;  
16.         printf("请输入要匹配的字符串的子串:\n");  
17.         std::cin >> t;  
18.     }  
19.     int Index_Kmp(int pos);  //字符匹配函数  
20. };  
21. #endif //KMPALGORITHM_H  

实现文件:KmpAlgorithm.cpp

[cpp]  view plain copy

1. #include "KmpAlgorithm.h"  
2. void KmpAlgorithm::Get_Next()  
3. {  
4.     int i,j;  
5.     i = 0;  
6.     j = -1;  
7.     next[0] = -1;  
8.     while(i < t.size()-1)  
9.     {  
10.         if(j == -1 || t[j] == t[i]) //如果相等则继续  
11.         {                           //next[0] == -1 j的值有可能回溯为-1数组越界  
12.             ++i;  
13.             ++j;  
14.             if(t[j] != t[i]) //如果下面两个字符不相等则把j的值赋给next在i位置的值  
15.                 next[i] = j;  
16.             else  
17.                 next[i] = next[j]; //相等则把next在j位置的值赋给next在i位置的值  
18.         }  
19.         else  
20.             j = next[j];  
21.     }  
22. }  
23. int KmpAlgorithm::Index_Kmp(int pos) //字符匹配函数  
24. {  
25.     int  i = pos - 1; //数组从下标0开始  
26.     int j = 0;  
27.     Get_Next();   
28.     while(i < s.size() && j < t.size())   
29.     {  
30.         if(j == -1 || s[i] == t[j]) //如果相等继续  
31.         {                           //如果j的值回溯到-1 next[0] == -1 则继续否则数组越界  
32.             ++i;  
33.             ++j;  
34.         }  
35.         else  
36.         {  
37.             j = next[j]; //不相等则回溯  
38.         }  
39.     }  
40.     if(j >= t.size()) //匹配成功返回在主串中的位置  
41.         return i - t.size() + 1;  
42.     else  
43.         return -1; //失败返回-1  
44. }  
45.       

测试文件:main.cpp

[cpp]  view plain copy

1. #include "KmpAlgorithm.h"  
2. #include <iostream>  
3. using namespace std;  
4. int main()  
5. {  
6.     int pos = 0;  
7.     KmpAlgorithm km;  
8.     printf("请输入在主串的第几个字符开始匹配:\n");  
9.     scanf("%d",&pos);  
10.     int position = km.Index_Kmp(pos);  
11.     if(position == -1)  
12.         printf("在主串中未找到与子串匹配的字符:\n");  
13.     else  
14.         printf("在主串的第%d个位置匹配成功\n",position);  
15.     return 0;  
16. }  

转自：http://blog.csdn.net/flying0033/article/details/6951316