好吧~KMP当初我也想了挺久的~很巧妙的算法啊!相必复制百科什么的你也不会看的了所以我手打吧…下面是我的理解~

　　为了解说方便我把长的称为文本串,短的称为目标串~

　　常规的匹配算法是把目标串一位一位地右移,跟文本串比较,而KMP则是跳着右移~

　　举几个例子相信你就懂了

　　————————————————————————————————————————

　　比如有一目标串为ababaca,当前位置匹配了前5个,也就是匹配了ababa,后面两个不匹配

　　这说明了文本串当前位置也是ababa

　　显然右移一位是不行的,因为从目标串可以看出(abab)a与a(baba)括号里的内容不相等

　　而右移两位是可能可行的~因为可以看出(aba)ba与ab(aba)括号里的内容是相等的,这意味着移动两位后,目标串前三位aba是肯定匹配的~因为移动前也匹配~

　　————————————————————————————————————————

　　再举一个例子~比如有目标串abcab,当前位置匹配了前两个ab

　　那么就需要右移3个位置,因为(ab)cab与abc(ab)括号里内容相同,移动后有可能会匹配~

　　————————————————————————————————————————

　　懂了么?表达能力有限…我也不能讲得更好了…具体代码网上一大堆,《算法导论》里面也有~我当初就是在算导里学会的!

　　如果懂了,希望有追加分啊,手打累死!

　　不懂的话,追问吧……

　　因为右移几位是通过观察，计算机实现的话是不是还要比较目标串自身？

　　我说的观察其实就是对目标串自身的初始化比较，通过对目标串的自身匹配可以计算出一个数组，这个数组里a[k]储存的是，当前匹配k个字母，需要右移多少个位置~