这可能是我见过的详细KMP教程

题目大意

传送门：http://poj.org/problem?id=3461
给定一个单词W和一段文本T，请统计单词W在文本T中的出现频率：要求所有连续字符与目标文本中的相应位置完全一致，并且允许相邻匹配结果产生交集。

思路分析

0

0

0

0

• 最直接的方法是逐一排查每一个元素。
  • 一旦发现第一个元素与 W【0

0

借用别人的图：

我们的匹配任务表示为：

这种方法的主要步骤是在出现匹配错误时将i指针移至下一个索引位置。由于我们的BC元素已经在之前的位置完成了匹配，在这种情况下并未利用已知的信息进行处理。

第二种方法如下：一旦出现主串匹配错误的情况时，并不会将索引i重新设置为第1位。这是因为，在主串发生失败位置之前（即当前指针指向的位置），除了第一个字符'A'之外，在此位置之前不会再有'A'字符存在。那么我们