串的模式匹配算法
问题:
求子串位置的定位函数如何写？ 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 }