Java實現基于Knuth-Morris-Pratt算法的回文串匹配

Knuth-Morris-Pratt（KMP）算法是一種高效的字符串匹配算法，它的時間復雜度為O(n+m)，其中n和m分別是文本串和模式串的長度

public class KMPAlgorithm {
    public static void main(String[] args) {
        String text = "ABABC";
        String pattern = "AB";
        int[] lps = computeLPSArray(pattern);
        int index = kmpSearch(text, pattern, lps);
        if (index != -1) {
            System.out.println("Pattern found at index: " + index);
        } else {
            System.out.println("Pattern not found");
        }
    }

    // 計算最長前綴后綴數組（LPS數組）
    public static int[] computeLPSArray(String pattern) {
        int[] lps = new int[pattern.length()];
        int len = 0;
        int i = 1;

        while (i < pattern.length()) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    // KMP搜索算法
    public static int kmpSearch(String text, String pattern, int[] lps) {
        int n = text.length();
        int m = pattern.length();
        int i = 0; // 指向text的指針
        int j = 0; // 指向pattern的指針

        while (i < n) {
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }

            if (j == m) {
                System.out.println("Pattern found at index: " + (i - j));
                j = lps[j - 1];
            } else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return -1; // 如果未找到模式串，返回-1
    }
}

這個程序首先計算模式串的最長前綴后綴數組（LPS數組），然后使用KMP搜索算法在文本串中查找模式串。如果找到模式串，程序將輸出其在文本串中的起始索引。