資料結構-String字元串比對(BM，KMP)

KMP

參考：https://baijiahao.baidu.com/s?id=1659735837100760934&wfr=spider&for=pc

// KMP
    public static int kmp(String str, String pattern) {
        // 預處理，生成next數組
        int[] next = getNexts(pattern);
        int j = 0;
        // 主循環，周遊主串字元
        for (int i = 0; i < str.length(); i++) {
            while (j > 0 && str.charAt(i) != pattern.charAt(j)) {
                //遇到壞字元時，查詢next數組并改變模式串的起點
                j = next[j];
            }
            if (str.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            if (j == pattern.length()) {
                //比對成功，傳回下标
                return i - pattern.length() + 1;
            }
        }
        return -1;
    }

    // 生成Next數組
    private static int[] getNexts(String pattern) {
        int[] next = new int[pattern.length()];
        int j = 0;
        for (int i = 2; i < pattern.length(); i++) {
            while (j != 0 && pattern.charAt(j) != pattern.charAt(i - 1)) {
                //從next[i+1]的求解回溯到next[j]
                j = next[j];
            }
            if (pattern.charAt(j) == pattern.charAt(i - 1)) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
           

String str = “ATGTGAGCTGGTGTGTGCFAA”;

String pattern = “GTGTGCF”;

int index = stringMatch.kmp(str, pattern);

System.out.println(“首次出現位置：” + index);

首次出現位置：12

BM

參考：https://blog.csdn.net/baidu_39502694/article/details/106475463

// BM算法比對字元串，比對成功傳回P在S中的首字元下标，比對失敗傳回-1
    public int bmMatch(String source, String pattern) {
        char[] src = source.toCharArray();
        char[] ptn = pattern.toCharArray();
        int sLen = src.length;
        int pLen = ptn.length;

        if (pLen == 0) {
            return 0;
        }
        if (sLen < pLen) {
            return -1;
        }
        int[] BC = buildBadCharacter(ptn);
        int[] GS = buildGoodSuffix(ptn);

        for (int i = pLen - 1; i < sLen; ) {
            int j = pLen - 1;
            for (; src[i] == ptn[j]; i--, j--) {
                if (j == 0) {
                    return i;
                }
            }

            // 每次後移“壞字元規則”和“好字尾規則”兩者的較大值
            // 注意此時i（壞字元）已經向前移動，是以并非真正意義上的規則
            i += Math.max(BC[src[i]], GS[pLen - 1 - j]);
        }

        return -1;
    }

    // 壞字元規則表
    public static int[] buildBadCharacter(char[] pattern) {
        int pLen = pattern.length;
        final int CHARACTER_SIZE = 256;
        int[] BC = new int[CHARACTER_SIZE];
        Arrays.fill(BC, pLen);
        for (int i = 0; i < pLen - 1; i++) {
            int ascii = pattern[i];
            BC[ascii] = pLen - 1 - i;
        }
        return BC;
    }

    // 非真正意義上的好字元規則表，後移位數還加上了目前好字尾的最大長度
    private static int[] buildGoodSuffix(char[] pattern) {
        int pLen = pattern.length;
        int[] GS = new int[pLen]; // 記錄好字尾出現時後移位數
        int lastPrefixPos = pLen; // 好字尾的首字元位置

        for (int i = pLen - 1; i >= 0; i--) {
            // i+1是主串begin（含）之後的子串是否比對模式串的字首
            if (isPrefix(pattern, i + 1)) {
                lastPrefixPos = i + 1;
            }
            GS[pLen - 1 - i] = lastPrefixPos + pLen - 1 - i;
        }
        // 上面在比較好字尾時，是從模式串的首字元開始的，但實際上好字尾可能出現在模式串中間。
        // 比如模式串EXAMPXA，假設主串指針在比較P時發現是壞字元，那麼XA就是好字尾，
        // 雖然它的首字元X與模式串的首字元E并不相等。此時suffixLen=2表示将主串指針後移至模式串末尾，
        // pLen-1-i=4表示真正的好字元規則，同樣主串指針後移，使得模式串前面的XA對齊主串的XA
        for (int i = 0; i < pLen - 1; i++) {
            int suffixLen = suffixLength(pattern, i);
            GS[suffixLen] = pLen - 1 - i + suffixLen;
        }

        return GS;
    }

    // 判斷是否是好字尾，即模式串begin（含）之後的子串是否比對模式串的字首
    private static boolean isPrefix(char[] pattern, int begin) {
        for (int i = begin, j = 0; i < pattern.length; i++, j++) {
            if (pattern[i] != pattern[j]) {
                return false;
            }
        }
        return true;
    }

    // 傳回模式串中以pattern[begin]（含）結尾的字尾子串的最大長度
    private static int suffixLength(char[] pattern, int begin) {
        int suffixLen = 0;

        int i = begin;
        int j = pattern.length - 1;
        while (i >= 0 && pattern[i] == pattern[j]) {
            suffixLen++;
            i--;
            j--;
        }

        return suffixLen;
    }
           

StringMatch stringMatch = new StringMatch();

int i = stringMatch.bmMatch(“HERE IS A SIMPLE EXAMPLE”, “EXAMPLE”);

System.out.println(“結果：”+i);

結果：17