Knuth-Morris-Pratt 算法

Knuth-Morris-Pratt 是一种字符串搜索算法，它使用预计算的数组在字符串中查找子串。这个数组被称为前缀函数。前缀函数是子串的最长前缀，同时也是该子串的后缀。前缀函数用于跳过已经匹配的字符。算法如下：

• 计算子串的前缀函数。
• 同时遍历字符串和子串。
• 如果字符匹配，则增加字符串和子串的索引。
• 如果字符不匹配，则将字符串的索引增加子串索引处的前缀函数值。