【算法】串的模式匹配算法（KMP）

串的模式匹配算法
     问题:
         求子串位置的定位函数如何写？ int index(SString S,SString T,int pos);
         给定串S，子串T，问T在S中从pos位开始第一次出现的位置是？

我没有使用字符数组或者string，而是自己实现SString，（这其实是数据结构作业）。S[0]中存放的是串的长度。

方法一：大暴力

 1 #include<iostream> 
 2 #include<cstdio>
 3 #define MAXSTRLEN 255
 4 typedef unsigned char SString[MAXSTRLEN+1]; //串的数组表示；注意： 0号存放串的实际长度，故这里是MAXSTRLEN+1 
 5 using namespace std;
 6 /*方法一：最简单的直接暴力 复杂度O(len(S)*len(T))*/
 7 int Index_simpal(SString S,SString T,int pos){
 8     int i = pos;
 9     int j = 1;
10     while(i<=S[0]&&j<=T[0]){
11         if(S[i] == T[i]){
12             ++i;
13             ++j;
14         }else{
15             //一旦匹配不上，子串从头开始找，S串从上一次开始匹配的下一个位置开始找 
16             j = 1;
17             i = i - (j-1) + 1;  //i是S串当前位置，j-1是当前匹配上的字符，i-(j-1)即上一次开始匹配的位置，+1即下一个位置 
18         }
19     }
20     if(j>T[0]){
21         //说明找到了
22         return i-T[0]; //第一次匹配上的下标，注意这里面所有下标都是自然计数（0存长度） 
23     }
24     return 0;
25 }

方法二：KMP算法

维护一个next数组，next[i] 是下标1到i之间的串的最大公共前缀后缀长度+1；

在方法一的基础上，不把子串重新遍历，而是从next[j] 处遍历；

母串S不从上一次开始匹配的地方开始，而是从当前位置继续；

具体看代码以及注释：　

 1 /*
 2     当不匹配时，不把i从上一次开始匹配的下一位开始寻找，而是从当前位开始寻找
 3     而子串j下标，不从头开始，而是从最大公共前后缀长度的下一位开始寻找
 4     这里引入最大公共前后缀的概念 当前匹配点之前的前、后缀相同的最大数值
 5     next数组就是+1
 6     自然计数 
 7     next[1] = 0;
 8 */
 9 #include<iostream> 
10 #include<cstdio>
11 #define MAXSTRLEN 255
12 typedef unsigned char SString[MAXSTRLEN+1]; //串的数组表示；注意： 0号存放串的实际长度，故这里是MAXSTRLEN+1 
13 using namespace std;
14 int next[100];
15 void get_next(SString T) {
16     next[1] = 0;
17     int i = 1;
18     int j = 0;
19     //遍历T 
20     while(i<T[0]) {
21         if(j == 0 ||T[i] == T[j]){
22             ++i;
23             ++j;
24             next[i] = j;
25         }else{
26             j = next[j];
27         }
28     }
29 }
30 
31 
32 int Index_KMP(SString S,SString T,int pos){
33     int i = pos;
34     int j = 1;
35     while(i<=S[0]&&j<=T[0]){
36         if(j == 0||S[i] == T[j]){
37             ++i;
38             ++j;
39         }else{
40             j = next[j]; //从第next[j]处开始找 
41         }
42     }
43     if(j>T[0]){
44         //说明找到了
45         return i-T[0]; //第一次匹配上的下标，注意这里面所有下标都是自然计数（0存长度） 
46     }
47     else return 0;
48 }
49 
50 
51 int main(){
52     SString s1 = "5abccd";
53     SString s2 = "2cd";
54     get_next(s1);
55     int ans = Index_KMP(s1,s2,1);
56     printf("%d",ans);
57 }

【算法】串的模式匹配算法（KMP）

相关推荐