KMP算法java版实现

Kahn 发布于2019-08-16 18:00 / 3516人阅读

摘要：原理代码部分匹配表匹配位置下一个比较位置记录所有匹配的子串记录子串匹配位置相等子串匹配完毕，记录位置，并且找下一个匹配的子串子串匹配位置加如果子串位置不匹配的话从匹配表里面找到子串新的匹配位置接着比较输出结果

原理：http://www.ruanyifeng.com/blo...
代码

import java.util.Arrays;

public class KMP {
    private static int[] prefixTable;

    /**
     * 部分匹配表
     * @param t
     * @return
     */
    public int[] getPrefixTable(char[] t){
        int n = t.length;
        int len;//匹配位置
        prefixTable = new int[n];
        prefixTable[0] = 0;

        for(int i = 1;i < n;i++){
            len  = prefixTable[i - 1];
            while(true){
                if(t[len] == t[i]){
                    len++;
                    prefixTable[i] = len;
                    break;
                }else{
                    if(len > 0)//下一个比较位置
                        len = prefixTable[len - 1];
                    else{
                        prefixTable[i] = 0;//
                        break;
                    }
                }
            }
        }
        return prefixTable;
    }

    public int[] match(char[] s,char[] t){
        int[] result = new int[s.length];//记录所有匹配的子串
        int count = 0;
        int j = 0;//记录子串匹配位置
        for(int i = 0;i < s.length;i++){
            if(s[i] == t[j]){//相等
                if(j == t.length - 1){//子串匹配完毕，记录位置，并且j=0找下一个匹配的子串
                    result[count++] = i - t.length + 1;
                    j = 0;
                }else{//子串匹配位置加1
                    j++;
                }
            }else{
                if(j > 0){//如果子串位置＞0
                    j = prefixTable[j - 1];//不匹配的话从匹配表里面找到子串新的匹配位置
                    i--;//接着比较
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        KMP kmp= new KMP();
        char[] s = "ABCDAB ABCDABCDABDEABCDABD".toCharArray();
        char[] t = "ABCDABD".toCharArray();
        kmp.getPrefixTable(t);
        int index[] = kmp.match(s, t);
        System.out.println(Arrays.toString(index));
    }
}

输出结果

[11, 19, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/74890.html

字符串匹配算法之KMP模式

摘要：字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。这篇文章主要是介绍KMP模式匹配算法，在正式介绍KMP之前我们先看一下普通模式匹配，由普通模式匹配在进一步的推导KMP模式会更容易理解。字符串的普通模式匹配普通模式匹配的原理不进行说明了，简单来说就是两个字符串的每个字符依次进行匹配。 public int match(String ...

NeverSayNever 2019-08-16 14:03 评论0 收藏0
[算法总结] 搞定 BAT 面试——几道常见的子符串算法题

摘要：第一种方法常规方法。如果不存在公共前缀，返回空字符串。注意假设字符串的长度不会超过。说明本题中，我们将空字符串定义为有效的回文串。示例输入输出一个可能的最长回文子序列为。数值为或者字符串不是一个合法的数值则返回。说明本文作者：wwwxmu 原文地址:https://www.weiweiblog.cn/13s... 作者的博客站点：https://www.weiweiblog.c...

chanjarster 2019-08-19 11:07 评论0 收藏0
数据结构-BF算法及KMP算法

摘要：算法代码复杂度最坏情况的时间复杂度。算法简单记忆分为两步模式串扫描，生成数组，。算法对算法的回溯问题进行了改进，在整个匹配过程中对主串仅需从头至尾扫描一遍。在定义函数时在参数前加上改为引传递。一般情况为值传递，对象除外。 BF算法代码复杂度最坏情况的时间复杂度O(m*n)。m为模式串长度。n为目标串长度。 KMP算法代码时间复杂度时间复杂度为O(m+n)。m为模式串长度...

jollywing 2019-06-27 16:20 评论0 收藏0
结合kmp算法的匹配动画浅析其基本思想

摘要：写在最前本次分享一下通过实现算法的动画效果来试图展示的基本思路。算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。本次主要通过动画演示的方式展现朴素算法与算法对比过程的异同从而试图理解的基本思路。写在最前本次分享一下通过实现kmp算法的动画效果来试图展示kmp的基本思路。欢迎关注我的博客，不定期更新中—— 前置概念字符串匹配字符串匹配是计算...

wpw 2019-08-22 14:51 评论0 收藏0