好吧~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个字母，需要右移多少个位置~