Java實現基于Boyer-Moore算法的回文串搜索

Boyer-Moore算法是一種高效的字符串搜索算法，它通過預處理模式串來跳過一些不必要的比較

public class BoyerMoorePalindromeSearch {

    public static void main(String[] args) {
        String text = "abccbaabc";
        String pattern = "abc";
        int index = search(text, pattern);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }

    public static int search(String text, String pattern) {
        if (text == null || pattern == null || text.length() < pattern.length()) {
            return -1;
        }

        // 預處理模式串
        int[] badCharacterShift = new int[256];
        preprocess(pattern, badCharacterShift);

        int i = 0; // text的索引
        int j = pattern.length() - 1; // pattern的索引

        while (i <= text.length() - pattern.length()) {
            if (pattern.charAt(j) == text.charAt(i)) {
                if (j == 0) {
                    return i; // 匹配成功
                }
                i++;
                j--;
            } else {
                int shift = badCharacterShift[text.charAt(i)];
                if (shift == 0) {
                    shift = pattern.length() - j;
                }
                i += Math.max(1, shift); // 跳過不需要比較的字符
                j = pattern.length() - 1;
            }
        }

        return -1; // 匹配失敗
    }

    private static void preprocess(String pattern, int[] badCharacterShift) {
        int m = pattern.length();
        for (int i = 0; i < m; i++) {
            badCharacterShift[pattern.charAt(i)] = m - i;
        }
    }
}

這個程序首先定義了一個search方法，該方法接受兩個字符串參數：text和pattern。preprocess方法用于預處理模式串，計算每個字符在模式串中最后出現的位置。在search方法中，我們使用雙指針技術從text和pattern的開頭開始比較字符。如果字符匹配，我們將指針向前移動；否則，我們根據badCharacterShift數組跳過一些不需要比較的字符。如果在text中找到了pattern，則返回其起始索引；否則，返回-1。