《算法与数据结构考研试题精析》笔记(4) - 串
做题要注意的问题
- 题目中的数组下标从0开始还是从1开始？
取巧
直接直观地移动模式串，寻找下一次开始匹配的位置。在一些客观题中，可有奇效。(管他黑猫白猫，可以捉住老鼠的就是好猫！)
规律
next数组中，对任意j大于1，都有next[j] > 0。（第一个元素一定为0）
next数组的实际用途以及如何使用见本文末的例子
在实际的KMP算法中，为了使公式更简洁、计算简单，如果串的位序从1开始，next数组才要整体加1；如果串的位序从0开始，那么next数组不需要整体加1.
记忆
【空串】空串(零个字符的串)是任何串的子串。
【子串】串中任意个连续的字符组成的子序列。要点一：字符串中包含的一段；要点二：一段字符串。
【非平凡子串】非空且不同于S本身的子串。
【子串的数目】n个互异的字符组成的串，共有个。(式子中的
+1，加上的是空串)
【存储方式】串既可以顺序存储，也可以链式存储。
【两字符串相等的充要条件】串的长度相等且两串对应字符相等。(或者说两个串的串值相等)
【空格串定义】由空格字符(ASCII码为32)组成的字符串。
求子串的定位函数Index(SString S, SString T, int pos)中，下标从1开始。返回值为子串T在主串S的第pos个字符之后第一次出现的位置，若没有出现，返回0。
串的一系列函数，pos都是第pos个字符，也就是说位序从1开始。
做题方法
【如何求next数组以及nextval数组】
- 求BM(用眼睛看，用眼睛看、比较，而不是计算)；
- 右移(用-1补充)、整体加1，得到next数组；
- 使用next数组求nextval数组。
但是求BM中，要小心点，很容易出错。
【求匹配次数】
- 如果没说使用KMP算法，那么就使用普通的模式匹配算法。
例
S = 'aabaabaabaac', T = 'aabaac'.
| j | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 模式 | a | a | b | a | a | c |
| BM | 0 | 1 | 0 | 1 | 2 | 0 |
| 右移 | -1 | 0 | 1 | 0 | 1 | 2 |
| next[j] | 0 | 1 | 2 | 1 | 2 | 3 |
第一趟：从主串S和模式串T的第一个字符开始比较，失配时i = 6，j = 6。
aabaabaabaac
aabaac
第二趟：next[6] = 3，主串当前位置和模式串的第3个字符b继续比较
aabaabaabaac
aabaac
第三趟：next[6] = 3，主串当前位置和模式串的第3个字符b继续比较
aabaabaabaac
aabaac