下面分别介绍：朴素模式匹配算法 和 改进模式匹配算法(KMP)
朴素模式匹配算法思想：
从目标S中的第一个字符开始和模式T中的的第一个比较（用 i 和 j 分别指示S串和T串中正在比较字符的位置），若相等，则继续逐个比较后续字符，否则， 从S 的第二字符重新开始匹配，直到匹配完成。
核心就是 i = i - j +1 ; //其中 j 就是已经匹配字符的个数 。+1 带表下一次匹配的位置。
///朴素匹配 #include<iostream> #include<cstdio> #include<cstring> using namespace std; int Index(char S[],char T[]){ int i,j; i=0;j=0; int lens=strlen(S); int lent=strlen(T); // cout<<lent<<" "<<lens; while(i<lens&&j<lent){ if(S[i]==T[j]){ i++; j++; } else{ i=i-j+1;///然现在T串已经匹配了j 的长度，所以直接将 i 回退 j 个长度 j=0; } } if(j=lent-1)///T 已经匹配结束，然后S 串中的起始位置 return i-lent; else return -1; } int main() { char S[10000]="afdfsdgdfbsderre"; char T[10000]="dgdf"; cout<<Index(S,T)<<endl; return 0; }
改进模式匹配算法(KMP)
时间复杂度O(n + m)
它的改进之处：每一趟匹配过程中出现字符比较不相等时，不需要回溯 i 值 ，而是利用已经的 “ 部分匹配” 的结果将 T(模式）向右 “滑动” 尽可能远的一段距离后在进行比较。 （用通俗的讲： 就是现在不需要将 i 值往会移动， 而是将 T(模式串) 往右移动。具体移动到到哪里就根据next[] 数组的值确定 ）
下面介绍如何求解模式串的next 数组值：
根据当位置的前 一个串 的 前缀和后缀串的最多匹配字符个数 //例如当前位置是 j , 就看 0 ~ j-1 这个串的前后缀最多匹配字符数
需要补充的是：0~j-1 这个串的前缀和后缀分别是 1~j-1 和 0~j-2 (意思就是前缀部包括第一个字符， 后最不包括最后一个字符)
求解以前： 自己需要根据题目要求， 设定 next 的起始位置的值， 有的是 0 ， 有的则是 以1 ； 具体就看 字符串的起始位置。
下面介绍next 索引 从0 开始
例如： abaabaac
首先 next[0] =0;
求 next[1] 的值得的时候， 我们就看 0~0 显然前缀和后缀串都是空串 所以是 0
next[1] =0;
求 next[2] 的值得的时候， 我们就看 0~1 显然前缀1~1和后缀串 0~0 ; 显然不匹配 所以
next[2]=0;
同理 next[3]=0;
求 next[4] 的值得的时候， 我们就看 0~3 显然前缀1~3和后缀串 0~2 ; 显然t[3]==t[0] =='a'
next[4]=1;
后面的依次类推。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int Maxsize =10000; void Get_next(char T[],int(&next)[Maxsize]){///next 的索引从0开始，获取next数组 int i=0,j=-1; next[0]=-1;///初始化 int len =strlen(T); while(i<len){ if(j==-1||T[j]==T[i]){ ++i; ++j; next[i]=j;/// } else j=next[j]; } } void Get_nextval(char T[],int (&nextval)[Maxsize],int next[]){///获取nextval int j=0; nextval[0]=-1;///初始化 int len =strlen(T); for(j=1;j<len;j++){ if(T[next[j]]==T[j]) nextval[j]=nextval[next[j]]; else nextval[j]=next[j]; } } int Index(char S[],int next[],char T[]){///进行模式匹配 int i=0,j=0; int len =strlen(S); int lent =strlen(T); while(i<len&&j<lent){ if((j==-1)||(S[i]==T[j])){ i++; j++; } else j=next[j]; } if(j==lent) return i-lent; else return -1; } int main() { int next[Maxsize]; int nextval[Maxsize]; char S[Maxsize]="afdfsdgdfbsderre"; char T[Maxsize]="bsder"; Get_next(T,next); Get_nextval(T,nextval,next); cout<<Index(S,next,T)<<endl;///通过next数组匹配获取位置信息 cout<<Index(S,nextval,T)<<endl;///通过nextval数组匹配获取位置信息 return 0; }
