栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

KMP算法Java实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

KMP算法Java实现

KMP算法又称模式串匹配:给定字符串partten,要求在字符串text中找到partten第一次出现的坐标并返回。

暴力匹配:
public int strStr(String text, String partten) {
        if (text.contains(partten)) {
            int n = partten.length();
            for (int i = 0; i < text.length(); i++) {
                if(text.substring(i, i+n) == partten){
                    return i;
                }
            }
        }
        return -1;
    }

时间复杂度是O(mn)

KMP比暴力匹配就在于,如果遇到不适配的字符,KMP知道退到哪里,而不是将partten已经适配的字符完全丢掉。具体过程如下:

我们知道KMP知道退回哪个位置的重点在于它记录了一个next数组,这个next数组具体怎么算的呢?

模式串pattern:ABABCABAA,要求next数组,必须先求pattern最长公共前缀后缀数组prefix:

parttenABABCABAA
prefix001201231

A:0

AB:0

ABA:1

ABAB:2

ABABC:0 

ABABCA:1

ABABCAB:2

ABABCABA:3

ABABCABAA:1

怎么用代码来实现这个prefix数组的求解呢??

i为pattern的索引,len是最长公共前后缀长度。初始i=1;len=0;

我们需要不断判断 pattern[i] 和 pattern[len] 是否相等

等的情况:

让len直接+1

不等的情况:因为当前i和len对应的字符不一样了,所以我们直接就让len等于它前一个prefix对应的长度了。

 最终代码实现得到最长公共前后缀数组:

// 根据模式串求出最长公共前后缀数组
    public int[] getPrefix(String needle) {
        int[] prefix = new int[needle.length()];
        prefix[0] = 0;
        int i = 1;
        int len = 0;
        while (i < needle.length()) {
            if (needle.charAt(i) == needle.charAt(len)) {
                len++;
                prefix[i] = len;
                i++;
            } else{
                if (len > 0) { // 只要当len大于0,减一,prefix下标才不会越界
                    len = prefix[len - 1];
                    prefix[i] = len;
                }else{ // 否则直接不处理
                    prefix[i] = len;
                    i++;
                }
            }
        }
        return prefix;
    }

如何根据prefix表得到next数组呢?prefix整体向后移动一位,第一个元素置为-1,最后一个prefix元素舍弃;

代码得到next数组:

// 根据最长公共前后缀得到模式串的next数组
    public int[] getNext(int[] prefix) {
        int[] next = new int[prefix.length];
        next[0] = -1;
        for (int i = 1; i < prefix.length; i++) {
            next[i] = prefix[i - 1];
        }
        return next;
    }

根据next数组进行模式匹配了:

i指向text,j指向pattern,

如果对应字符适配,则:i++,j++;

如果不适配,则j = next[j],如果j==-1,则j++,i++;

代码实现:

public int search(String haystack, String needle) {
        int[] prefix = getPrefix(needle);
        int[] next = getNext(prefix);

        int i = 0;
        int j = 0;
        while (i < haystack.length() && j < needle.length()) {
            if (haystack.charAt(i) == needle.charAt(j)) { // 适配,i和j同时前移
                i++;
                j++;
            } else { // 不适配,j后退
                j = next[j];
                if (j == -1) { // 如果j后退到-1,说明j处于pattern的其实位置,那么i和j就同时前移
                    j++;
                    i++;
                }
            }
        }
        if (j == needle.length()) {
            return i - needle.length();
        }
        return -1;
    }

结束。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/956877.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号