算法一：朴素的模式匹配算法
假设要找到主字符串s='goodgoogle '到t='google '的子字符串的位置，需要执行以下步骤
1、从主串s的第一位开始，s和t的前三个字都成功匹配，第四个字不匹配(竖线表示相等，表示不想像闪电一样弯曲) )。
2、从主串s的第2位开始匹配失败
3、从主串s的第三位开始匹配失败
4、从主串s的第4位开始匹配失败
5、从主串s的第5位开始，s和t、6个字符全部匹配成功
主字符串中的每个字符都以子字符串开始，并与匹配字符串匹配。 在主字符串中创建一个大循环，并在每个字符的开头创建一个t长的小循环。 继续，直到匹配成功或所有路径都完成。
# includeiostreamusingnamespacestd； //返回主串t的第pos字符以后的子字符串t的位置； 如果不存在，函数返回0//t非空，1poss.size(intindex(strings，string t，int pos=0) /默认值为0，默认值从第一个元素开始{int i=pos //主串t当前下表int j=0； //子字符串t当前下表while(is.size ) (jt.size ) ) )/I小于s长度，j小于t长度，循环继续(if(s(I )==t(j ) ) I； j； (}返回}else//指针并重新开始匹配) I=I-j1； //i返回到与上次顶部匹配的下一个j=0//j返回到子字符串t的顶部}if(j=t.size () ) return i - t.size ) 1； //i - t.size ) )表示来自s[4]的重复，1是该元素为第5个元素的elsereturn 0； }int main () {string s='goodgoogle '； string t='谷歌'； 计数索引(s，t ) endl； 返回0； }复杂度：
最好的，比如在“谷歌谷歌”上找“谷歌”，时间复杂度是o(1)
虽然有点不好，但是例如在“abcdefgoogle”中查找“google”，时间复杂度是o(n m )，其中n是主串长度，m是副串长度，根据等概率的原则，平均查找(n m )的话
最坏情况发生在字符串t的最后一个字符，例如部分字符串t='0000000001 '、9个'0'和1个'1'
主串s=' 00000000000000000000000000000000000000000000000000000000001 '，49个'0'和1个'1'
时间复杂度为o((n-m1 ) (m ) ) ) ) ) )。
算法二：KMP模式匹配算法
设主串s='abcdefgab '，t='abcdex '
意味着" abcdex "开头字符" a "不等于后续的字符串" bcdex "中的任一个，子串t和主串s的前5个字符分别相等，子串t的开头字符" a "不能与s列的第2位到第5位的字符相等
在上面的情况中，子字符串t中没有重复的字符。 给出一个有重复字符的例子
假设s='abcababca '，t='abcabx '
在第一步中，前五个字符相等，第六个字符不相等。 根据以前的经验，t的首字母' a '没有必要判断为t的第2位、第3位的文字军部等
部分列t的第1位和第4位相等，第2位和第5位相等； 主列s中第4位、第5位分别与副列t中的第4位、第5位相等，意味着副列的第1位和第2位分别与主列的第4位和第5位相等，不需要判断
总之，I值不回溯，j值的变化只与子串有关，取决于t列中的结构是否有重复的字符串。
将t字符串各位置的变化定义为一个数组next，next的长度是t字符串的长度
以next数组为例。
# includeiostreamusingnamespacestd； //通过计算，子字符串的next数组voidget_next(stringt，int *next ) {int i，j； i=1； j=0； next[1]=0； while(it.size(-1 ) if ) j==0||t[I]==t[j] )//t[i]是后缀的单个字符，t[j]是前缀的单个字符) I； j； next[i]=j； }elsej=next[j]； 如果//字符不相同，则返回j值回溯}//主字符串t的第pos字符以后的部分字符串t的位置； 如果不存在，函数必须返回0//s[0]和t[0]以保存字符串的长度。 其中#intindex_kmp(strings，string t，int pos=1) /默认情况下，从主字符串的第一个位置开始搜索。 (因为inti=pmp //i表示主串s的当前位置int j=1； //j表示子字符串t的当前位置int next[255]； //定义
一个next数组get_next(t, next);//对串做分析，得到next数组while (i < s.size() && j < t.size())//若i小于s的长度且j小于t的长度，循环继续{if (j == 0 || s[i] == t[j])//两字符串相等，或j处于开始位，继续{i++;j++;}else//j值退回合适的位置，i值不变j = next[j];}if (j >= t.size())return i - t.size() + 1;elsereturn 0;}int main(){string s = "#goodgoogle";string t = "#google";cout << Index_KMP(s, t) << endl;return 0;}时间复杂度：对于get_next来说，t的长度为m，由于只涉及到简单循环，其时间复杂度为O(m)；i的值不回溯，主串的长度为n，while循环的时间复杂度为O(n)，因此整个代码的数减复杂度为O(n+m)
算法三：KMP模式匹配算法改进
KMP匹配算法还是有缺陷的，比如子串s="aaaabcde"，子串t="aaaaax"，子串t的next为012345
我们发现②③④⑤步骤是多余的。由于子串t中第2、3、4、5个位置上的字符串和守卫上的字符串相等，那么可以用首位next[1]来代替后续与它相等的字符后续的next[j]
取代的数组为nextval[]，代码如下
#include<iostream>using namespace std;//求模式串t的next函数修正值并存入数组nextvalvoid get_nextval(string t, int *nextval){int i, j;i = 1;j = 0;nextval[1] = 0;while (i<t.size() - 1){if (j == 0 || t[i] == t[j])//T[i]表示后缀的单个字符，T[j]表示前缀的单子字符{i++;j++;if (t[i] == t[j])//若当前字符与前缀字符相等{nextval[i] = nextval[j];//将前缀字符的nextval值赋值给nextval在i位置上的值}elsenextval[i] = j;//当前的j为nextval在i位置上的值}elsej = nextval[j];//不相等，j回溯}}int Index_KMP(string s, string t, int pos = 1){int i = pos;int j = 1;int next[255];get_nextval(t, next);while (i < s.size() && j < t.size()){if (j == 0 || s[i] == t[j]){i++;j++;}elsej = next[j];}if (j >= t.size())return i - t.size() + 1;elsereturn 0;}int main(){string s = "Agoodgoogle";string t = "3google";cout << Index_KMP(s, t) << endl;return 0;}