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