前缀函数和 KMP "跳步骤"模式匹配

在一篇由字符构成的长文中查找另一个短字符串出现的位置，这可以算是编程领域最最常见的问题（比如按下 Ctrl + F 就可以打开你浏览器的查找功能）。这个问题叫做字符串的模式匹配，我们把被查找的关键词叫做模式串，被查找的全文叫做主串。注意：本文的下标均从 0 开始。
当我们用最容易想到的朴素的暴力解法时，就像逐字逐句地翻动书页：将模式串的每个字符与主串逐一比对，一旦发现不匹配，就把模式串右移一位，重新从头比较。

面对随机数据，算法可以高效工作。但这种老实人的做法，在遇到某些“狡猾”的数据时会彻底崩溃。比如：

• 主串：AAAAA……AAB（连续100万个A后跟一个B）
  
• 模式串：AAAAAAAC
  

暴力解法会怎么做？它会在主串的每一个位置，逐个对比前7个字符，直到发现第7位的A与C不匹配，再右移一位重复这个过程，最终一共进行了八百万次匹配，最终还是没有找到。


来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！