串的模式匹配

子串的定位操作通常称为串的模式匹配，它求的是子串(常称模式串)在主串中的位置。

子串——主串的一部分，一定存在

模式串——不一定能在主串中找到

朴素模式匹配

将主串中所有长度为m的子串（共有n-m+1个）依次与模式串对比，直到找到一个完全匹配的子串，或所有的子串都不匹配位置。主串长度为n，模式串长度为m。

我们尝试不使用字符串的基本操作，直接通过数组下标实现朴素模式匹配算法——使用双指针暴力遍历模式串、主串进行匹配。

若当前子串匹配失败，则主串指针i指向下一个子串的第一个位置 $i=i-j+2$ ，模式串指针j回到模式串的第一个位置 $j=0$

若 $j>T.length$ ，则当前子串匹配成功，返回当前子串第一个位置的字符 $j-T.length$

代码实现

int Index(SString S, SString T) {int i = 1, j = 1;while (i <= S.length&&j <= T.length) {if (S.ch[i] == T.ch[j]) {++i, ++j;}else {i = i - j + 2;j = 1;}}if (j > T.length)return i - T.length;elsereturn 0;
}

最坏时间复杂度为 $O(mn)$

KMP算法

在上面的简单匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断地进行自我比较，这就是其低效率的根源。
因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无须回溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

KMP特点：仅仅后移模式串，比较指针不回溯。

算法流程

1.根据模式串T，求出next数组

2.利用next数组进行匹配（主串指针不回溯）

算法实现

int Index_KMP(SString S, SString T,int next[]) 
{int i = 1, j = 1;while (i <= S.length && j <= T.length){if (S.ch[i] == T.ch[j]){++i;++j;}//某次匹配结束后if (j == 0){++i;++j;}else j = next[j];}if (j > T.length)return i - T.length; //匹配成功elsereturn 0;
}

最坏时间复杂度 $O(m+n)$

求next数组（手算）

next数组的作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配。

任何模式串都一样，第1个字符不匹配时，只能匹配下一个子串，因此，next[1]都写0。

任何模式串都一样，第2个字符不匹配时，应尝试匹配模式串的第1个字符，因此，next[2]都写1。

在不匹配的位置前边，划一根美丽的分界线模式串一步一步往后退，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时 j 指向哪儿，next数组值就是多少。

void get_next(String T, int *next){int i = 1, j = 0;next[1] = 0;while (i < T.length){if(j==0 || T.ch[i]==T.ch[j]){	//ch[i]表示后缀的单个字符，ch[j]表示前缀的单个字符++i; ++j;next[i] = j;	//若pi = pj， 则next[j+1] = next[j] + 1}elsej = next[j];	//否则令j = next[j]，j值回溯，循环继续}
}