Ta上传的资源 (0)

kmp算法是一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是根据给定的模式串W1,m,定义一个next函数。next函数包含了模式串本身局部匹配的信息

/*分治法思想:将一个n规模的问题分解成k个规模较小的子问题,并且这些子问题之间都是相互独立的,通过递归求解这些子问题,然后将子问题的解合并,就可以得到原问题的解。

/*动态规划法思想:将较大的问题分解成较小的问题,先求解子问题,然后通过子问题的解得到原问题的解,经过分解的子问题之间并不是相互独立的。*/

从主串S的第一个字符开始和模式T的第一个字符进行比较,若相等,则继续比较两者的后续字符;若不相等,则从主串S的第二个字符开始和模式T的第一个字符进行比较,重复上述过程,若T中的字符全部比较完毕,则说明本趟匹配成功;若S中的字符全部比较完毕,则匹配失败。这个算法称为朴素的模式匹配算法,简称BF算法