應用場景-字元串比對問題

舉例：判斷兩個字元數組是否比對，比對的話，傳回出現位置的下标

暴力比對

代碼示例：

package com.wxit.kmp;

/**
 * @Author wj
 * 暴力比對算法
 **/
public class ViolenceMatch {

    public static void main(String[] args) {
        //測試暴力比對算法
        String str1 = "輕輕的風兒輕輕地吹";
        String str2 = "風兒";                                                                 

        int index = violenceMatch(str1, str2);
        System.out.println("index=" + index);
    }

    //暴力比對算法的實作
    public static int violenceMatch(String str1,String str2){
        char[] s1 = str1.toCharArray();
        char[] s2 = str2.toCharArray();

        int s1Len = s1.length;
        int s2Len = s2.length;

        int i = 0;//i索引指向s1
        int j = 0;//j索引指向s2

        while (i < s1Len && j < s2Len){//保證比對時，不越界
            if (s1[i] == s2[j]){//比對OK
                i++;
                j++;
            } else { //沒有比對成功
                i = i - (j - 1);
                j = 0;
            }
        }

        //判斷是否比對成功
        if (j == s2Len){
            return i - j;
        }else {
            return -1;
        }
    }
}
           

KMP算法

KMP算法介紹

KMP是一個解決模式串在文本串是否出現過，如果出現過，最早出現的位置的經典算法

KMP方法算法就利用之前判斷過資訊，通過一個next數組，儲存模式串中前後最長公共子序列的長度，每次回溯時，通過next數組找到，前面比對過的位置，省去了大量的計算時間

參考資料：

https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html

package com.wxit.kmp;

import java.util.Arrays;

/**
 * @Author wj
 **/
public class KMPAlgorithm {

    public static void main(String[] args) {
        int next[] = kmpNext("ABCDABD");
        System.out.println("next=" + Arrays.toString(next));

        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

        int index = kmpSearch(str1, str2, next);
        System.out.println(index);
    }

    //擷取到一個字元串(子串)的部分比對值表
    public static int[] kmpNext(String dest){
        //建立一個next數組儲存部分比對值
        int next[] = new int[dest.length()];
        next[0] = 0;//如果字元串長度為1，部分比對值就是0
        for (int i = 1,j = 0; i < dest.length(); i++) {
            //當dest.charAt(i) != dest.charAt(j),我們需要從next[j - 1]擷取新的j
            //直到我們發現有dest.charAt(i) == charAt(j)成立才退出
            //這是kmp算法的核心
            while (j > 0 && dest.charAt(i) != dest.charAt(j)){
                j = next[j - 1];
            }
            //當dest.charAt(i) == dest.charAt(j)滿足時,部分比對值就是+1
            if (dest.charAt(i) == dest.charAt(j)){
                j++;
            }
            next[i] = j;
        }
        return next;
    }

    //寫出kmp搜尋算法
    /**
     *
     * @param str1  源字元串
     * @param str2  子串
     * @param next  部分比對表，是子串對應的部分比對表
     * @return  如果是-1就是沒有比對到，否則傳回第一個比對的位置
     */
    public static int kmpSearch(String str1,String str2,int[] next){
        //周遊
        for (int i = 0,j = 0; i < str1.length(); i++) {
            //需要處理str1.charAt(i) ！= str2.charAt(j),調整j的大小
            while (j > 0 && str1.charAt(i) != str2.charAt(j)){
                j = next[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)){
                j++;
            }
            if (j == str2.length()){
                return i - j + 1;
            }
        }
        return -1;
    }
}