问题描述

串的模式匹配就是子串定位操作。给定两个串s="s0 s1 ... s(n-1)"和t="t0 t1 ... t(m-1)"（其中n和m分别是串s和t的长度），在主串s中寻找子串t的过程称为模式匹配，t称为模式。如果在s中找到等于t的子串，则称匹配成功，返回t在s中的首次出现的下标位置；否则匹配失败，返回-1。

本文介绍三个串模式匹配算法，分别是简单回溯算法（Brute-Force，BF算法）、KMP算法、KMP算法的改进。

1 BF算法

从主串s的第0个字符开始，与模式串t的第0个字符开始逐字符比较，不相同时回溯到模式串t的第0个和主串s的第1个字符，重新开始比较。以此类推，直到t的所有字符完成匹配，则匹配成功，否则匹配失败。

BF算法

2 KMP算法

BF算法速度慢的原因是存在大量不必要的回溯，即在某一趟与t的匹配过程失败后，需要返回s串开始字符的下一字符重新开始比较，这对于某些模式串t来说是不必要的。例如，若s=12123123132，t=12313，在t与12123123132中加粗子序列进行比较时，在2处发生失配，BF算法接下来将t与12123123132、12123123132、12123123132比较。由于t中的231、312与其开始的123并不相同，显然t与12123123132、12123123132的比较是不必要的。

KMP算法就是利用模式串中与模式串开头部分子串的重复性来减少重复回溯，实现新一轮比较的直接跳转。具体来说，KMP算法利用一个数组记录模式串中每一个字符前面有几个字符与模式串从头重复，在与s串比较失配时，直接跳转到重复子串的下一个字符继续比较，而不用跳转至模式串t的第0个字符。

KMP算法只在面对某种特定的模式串时比BF算法有更高的效率。

即要求模式串存在重复性的子串，且必须从头开始重复，例如abcabd，abcad等，诸如abcbc这种的也无效。

算法步骤：①计算跳转数组next。②利用KMP算法进行模式匹配。

next数组通过递推计算，即如果当前字符t[j]的前一个字符t[j-1]与其next[j-1]指向的字符t[next[j-1]]相同，意味着t[j]前的next[j-1]+1个字符与从t[0]到t[next[j-1]]的子串相同，因此next[j]=next[j-1]+1；如果不相同，则递推至t[next[j-1]]的next值指向的字符，与t[j-1]比较，直到确认t[j]前与t串从头重复的字符数，或者无重复字符标记为0。

getnext函数的实现

注意此处的函数返回参数类型为int*，用于返回一位数组，且返回的这个一位数组必须在函数中用static定义。

KMP算法进行模式匹配时，只需在回溯时将j指针赋值为next[j]。需要注意的是，若next[j]为-1，则意味着t[j]前面没有与t从头重复的字符，且t[j]与s[i]失配，则i和j均加1。

KMP算法的实现

3 KMP算法的改进

考虑更特殊的模式串，还能进一步减少不必要的回溯次数。例如，s=111211112，t=11112，按照上述next的计算方式，next={-1,0,1,2,3}。当i=3, j=3时失配，此时s[i]=2, t[j]=1，由于next[j]=2，于是j跳转为2，t=11112与s=111211112比较。由于t[next[j]]=t[j]也为1，必然与s[i]=2不相同，显然这次回溯也不必要。

总结来说，当失配的字符与待跳转的字符相同时，跳转一步并无意义，可再跳一步，即将当前字符置为跳转后字符的next值。

getnext函数的改进