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

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

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

方法一：大暴力

 #include<iostream>

 #include<cstdio>

 #define MAXSTRLEN 255

 typedef unsigned char SString[MAXSTRLEN+]; //串的数组表示；注意： 0号存放串的实际长度，故这里是MAXSTRLEN+1

 using namespace std;

 /*方法一：最简单的直接暴力 复杂度O(len(S)*len(T))*/

 int Index_simpal(SString S,SString T,int pos){

     int i = pos;

     int j = ;

     while(i<=S[]&&j<=T[]){

         if(S[i] == T[i]){

             ++i;

             ++j;

         }else{

             //一旦匹配不上，子串从头开始找，S串从上一次开始匹配的下一个位置开始找

             j = ;

             i = i - (j-) + ;  //i是S串当前位置，j-1是当前匹配上的字符，i-(j-1)即上一次开始匹配的位置，+1即下一个位置

         }

     }

     if(j>T[]){

         //说明找到了

         return i-T[]; //第一次匹配上的下标，注意这里面所有下标都是自然计数（0存长度）

     }

     return ;

 }

方法二：KMP算法

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

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

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

具体看代码以及注释：　

 /*

     当不匹配时，不把i从上一次开始匹配的下一位开始寻找，而是从当前位开始寻找

     而子串j下标，不从头开始，而是从最大公共前后缀长度的下一位开始寻找

     这里引入最大公共前后缀的概念 当前匹配点之前的前、后缀相同的最大数值

     next数组就是+1

     自然计数

     next[1] = 0;

 */

 #include<iostream>

 #include<cstdio>

 #define MAXSTRLEN 255

 typedef unsigned char SString[MAXSTRLEN+]; //串的数组表示；注意： 0号存放串的实际长度，故这里是MAXSTRLEN+1

 using namespace std;

 int next[];

 void get_next(SString T) {

     next[] = ;

     int i = ;

     int j = ;

     //遍历T

     while(i<T[]) {

         if(j ==  ||T[i] == T[j]){

             ++i;

             ++j;

             next[i] = j;

         }else{

             j = next[j];

         }

     }

 }

 int Index_KMP(SString S,SString T,int pos){

     int i = pos;

     int j = ;

     while(i<=S[]&&j<=T[]){

         if(j == ||S[i] == T[j]){

             ++i;

             ++j;

         }else{

             j = next[j]; //从第next[j]处开始找

         }

     }

     if(j>T[]){

         //说明找到了

         return i-T[]; //第一次匹配上的下标，注意这里面所有下标都是自然计数（0存长度）

     }

     else return ;

 }

 int main(){

     SString s1 = "5abccd";

     SString s2 = "2cd";

     get_next(s1);

     int ans = Index_KMP(s1,s2,);

     printf("%d",ans);

 }

巴特西

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

最新文章

热门文章