第四章串

1、串的模式匹配
子串的定位操作通常称为串的模式匹配，他求的是子串在主串中的位置。
暴力模式匹配算法的思想使：从主串的第一个字符起，与子串的第一个字符比较，相等则继续比较；不能则从主串的下一个位置起，继续和子串开始比较，直到最后看是否匹配成功。
改进的模式匹配算法——KMP算法：
在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而每趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串再不断地进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串指针无须回溯，并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身结构有关，与主串无关。