KMP算法java版實現

Kahn 發布于2019-08-16 18:00 / 3539人閱讀

摘要：原理代碼部分匹配表匹配位置下一個比較位置記錄所有匹配的子串記錄子串匹配位置相等子串匹配完畢，記錄位置，并且找下一個匹配的子串子串匹配位置加如果子串位置不匹配的話從匹配表里面找到子串新的匹配位置接著比較輸出結果

原理：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]

GPU云服務器云服務器 kmp算法圖像識別 kmp算法php代碼字符串的kmp算法字符串kmp算法c

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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