栈在递归中的应用

串的模式匹配

子串的定位操作通常称为串的模式匹配

子串称为模式串，即在主串中找子串（模式串）。

915考纲中要求掌握模式匹配的两个算法：Brute-Force和KMP。

---

Brute-Force（暴力）

暴力模式匹配算法的最坏时间复杂度为$O(nm)$，其中$n$和$m$分别为主串和模式串长度。

---

KMP

浅谈KMP算法 | Lzc’s blog (lizc.cn)

求next数组

计算方法：

1. 前两个是next数组值是01
2. max[n个前缀 = n个后缀] 写 n+1
3. 前后缀不相等，写 1

求第i个值时，要看i之前的字符。

求ababaaababaa：

a：0

ab：01

aba：011 （ab的前后缀不相等，值1）

abab：0112 （aba的最大相等前后缀为a，n=1，值为n+1）

…

ababaaababaa：011234223456

求nextval数组

求nextval值需要next值。

计算方法：

1. 第1位：0
2. 第2位若与第1位相同为0，不同为1
3. 从第3位开始，根据next值
   • 相同：
   • 不同：当前next值

求s = abaabcac：

next值：01122312

a：0

ab：01 （与第一位不同，为1）

aba：010 （此时next[3] = 1，且s[1] = ‘a’，这与当前s[3]字符相同，则此处的nextval值就为nextval[1]，也就是0）

abaa：0102 （此时next[4] = 2，且s[2] = ‘b’，这与当前s[4]字符不同，则此处的nextval值就为next[4]，也就是2）

abaab：01021 （此时next[5] = 2，且s[2] = ‘b’，这与当前s[5]字符相同，则此处的nextval值就为nextval[2]，也就是1）

abaabc：010213 （由next[6]可知两个字符不相同，因此此处值为next[6]）

abaabca：0102130 （相同，所以为nextval[1]，此处为0）

abaabcac：01021302 （不同）

最终的nextval值为：01021302