KMP算法基础知识，数据结构
KMP算法是一种字符串搜索算法，旨在解决字符串中是否包含另一个字符串的问题。在给定的文件中，我们可以看到一个字符串"BBC ABCDAB ABCDABCDABDE"，我们想知道是否包含另一个字符串"ABCDABD"。
KMP算法的主要思想是，设法利用已知信息，不要把"搜索位置"移到已经比较过的位置，继续把它向后移，这样就提高了效率。为此，需要建立一张《部分匹配表》（Partial Match Table），该表是根据搜索词生成的。
《部分匹配表》的产生基于两个概念："前缀"和"后缀"。"前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。
例如，以"ABCDABD"为例，"部分匹配值"可以通过计算得到：
* "A"的前缀和后缀都为空集，共有元素的长度为 0；
* "AB"的前缀为[A]，后缀为[B]，共有元素的长度为 0；
* "ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度 0；
* "ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为 0；
* "ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA,A]，共有元素为"A"，长度为 1；
* "ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为 2；
* "ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为 0。
通过《部分匹配表》，我们可以快速地移动搜索词的位置，从而提高搜索的效率。在搜索过程中，我们可以根据已匹配的字符数和对应的"部分匹配值"，计算出搜索词的移动位数。
例如，在搜索词"ABCDABD"中，已知空格与 D 不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符 B 对应的"部分匹配值"为 2，因此按照下面的公式算出向后移动的位数：移动位数 = 已匹配的字符数 - 对应的部分匹配值因为 6 - 2 等于 4，所以将搜索词向后移动 4 位。
通过 KMP 算法，我们可以快速地搜索字符串，提高搜索的效率。
