溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》

Java實現(xiàn)基于Knuth-Morris-Pratt算法的回文串匹配

發(fā)布時間:2024-11-11 18:35:43 來源:億速云 閱讀:78 作者:小樊 欄目:編程語言

Knuth-Morris-Pratt(KMP)算法是一種高效的字符串匹配算法,它的時間復(fù)雜度為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");
        }
    }

    // 計算最長前綴后綴數(shù)組(LPS數(shù)組)
    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
    }
}

這個程序首先計算模式串的最長前綴后綴數(shù)組(LPS數(shù)組),然后使用KMP搜索算法在文本串中查找模式串。如果找到模式串,程序?qū)⑤敵銎湓谖谋敬械钠鹗妓饕?/p>

向AI問一下細節(jié)

免責聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI