KMP算法

xiaoxiao2021-02-28  15

1. 朴素算法(比较是一位一位比的,计算机二进制比的效率很慢) 2.KMP算法 避免重复比较,及上图去掉2/3步骤 实现方法,先算next值: next算法如下: k = 0 (第一位) 若有 P(1)【P(1)代表第一位的A】 ~ P(K-1) = P(J-K+1) ~ P(J-1),则next值为K (就是比方说看第五位的B,要看他前面的四位,发现有一个a和第一位的a重复,那么就得了2,比方说看x 前面如果是 abcab,则看到有ab和最前面的ab重复,那么就得3了) 代码感受下: 3. KMP算法优化。 比如: 这样的话,比较i[x] != j[x]时,前面a是相同的,KMP算法会回溯到上一个a进行比较,而改良版的KMP算法会回溯到第一个a进行比较。保证了回溯到最前面的循环体。
转载请注明原文地址: https://www.6miu.com/read-2450047.html

最新回复(0)