菜单 学习猿地 - LMONKEY

VIP

开通学习猿地VIP

尊享10项VIP特权 持续新增

知识通关挑战

打卡带练!告别无效练习

接私单赚外块

VIP优先接,累计金额超百万

学习猿地私房课免费学

大厂实战课仅对VIP开放

你的一对一导师

每月可免费咨询大牛30次

领取更多软件工程师实用特权

入驻
170
0

KMP算法

原创
05/13 14:22
阅读数 45042

  KMP算法是一种改进的字符串匹配算法。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数,函数本身包含了模式串的局部匹配信息。

  next()函数的作用,就是在模式串中,找出最长的相同前缀,形成一张跳转表。

  跳转表的用途是,当目标串target中的某个子部target[m...m+(i-1)]与pattern串的前i个字符pattern[1...i]相匹配时,如果target[m+i]与pattern[i+1]匹配失败,程序不会像朴素匹配算法那样,将pattern[1]与target[m+1]对其,然后由target[m+1]向后逐一进行匹配,而是会将模式串向后移动i+1 - next[i+1]个字符,使得pattern[next[i+1]]与target[m+i]对齐,然后再由target[m+i]向后与依次执行匹配。

public static int[] getNext(String b) {
    int len = b.length();
    int j = 0;
    int next[] = new int[len + 1];

    next[0] = next[1] = 0;

    for (int i = 1; i < len; i++) {
        while (j > 0 && b.charAt(i) != b.charAt(j))
            j = next[j];
        if (b.charAt(i) == b.charAt(j))
            j++;
        next[i + 1] = j;
    }
    return next;
}

 

发表评论

0/200
170 点赞
0 评论
收藏
为你推荐 换一批