kmp算法(十分钟理解)
本文并不打算细说kmp算法的算法实现,而是通过几张图来描述kmp算法的思想。
现在我们将两个字符串左对齐,然后依次对比每位是否相等
当遇到不匹配时需要将P整体往右移动
现在需要移动1位然后依次对比每位是否相等,不相等就又需要整体往右移1位。那可以每次尽可能的向右多移动几位吗?
如果我们提前就可以算出移动几位后才会开始匹配,这样匹配就可以加速了。从上图可以看出移动两位后可以向前继续匹配的,因为此时前面的对应位子字符是相等的。
下图说明了在第6位不匹配时可以向右移2位的计算过程。
针对需要查找的字符串P我们可以算出在每一位不匹配时,可以向右移动的最远长度