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。