Rabin-Karp算法

Rabin-Karp算法是一種基於哈希函數的字符串匹配算法，由 Michael O. Rabin 和 Richard M. Karp 於1987年提出，核心思想是用哈希函數將模式串和文本串中的子串轉換為數值進行比較，避免大量不必要的字符比較。這個算法特別適合多模式串匹配場景，時間複雜度平均為O(n+m)，n是文本串長度，m是模式串長度。

Rabin-Karp算法的關鍵在於使用滾動哈希函數（Rolling Hash），它可以在常數時間內計算出滑動窗口的新哈希值，保證算法在大多數情況下的高效性。

算法步驟

1. 計算模式串的哈希值
2. 計算文本串中長度為m的第一個子串的哈希值（m為模式串長度）
3. 在文本串上滑動窗口，對於每個位置：
   • 使用滾動哈希技術高效計算當前窗口的哈希值
   • 如果哈希值與模式串相等，則進行字符逐一比較以避免哈希衝突
   • 如果完全匹配，則找到一個匹配位置
4. 重複步驟3，直到處理完整個文本串

核心特性

• 基於哈希比較：通過哈希值比較代替直接字符比較
• 滾動哈希：O(1)時間複雜度計算下一窗口的哈希值
• 時間複雜度：平均情況O(n+m)，最壞情況O(n*m)
• 空間複雜度：O(1)，只需常數額外空間
• 適用範圍：單模式和多模式串匹配場景，特別是多模式匹配

基礎實現

接下來大家一起看下Rabin-Karp算法的部分主流語言實現：

public class RabinKarp {
    private final static int PRIME = 101; // 哈希計算使用的質數
    
    public static int search(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // 計算哈希乘數，等於d^(m-1) % PRIME，用於滾動哈希計算
        int h = 1;
        for (int i = 0; i < m - 1; i++) {
            h = (h * 256) % PRIME;
        }
        
        // 計算模式串和第一個窗口的哈希值
        int patternHash = 0;
        int textHash = 0;
        for (int i = 0; i < m; i++) {
            patternHash = (256 * patternHash + pattern.charAt(i)) % PRIME;
            textHash = (256 * textHash + text.charAt(i)) % PRIME;
        }
        
        // 滑動窗口，比較哈希值
        for (int i = 0; i <= n - m; i++) {
            // 哈希值相等時，檢查是否真正匹配
            if (patternHash == textHash) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return i; // 找到匹配
                }
            }
            
            // 計算下一個窗口的哈希值
            if (i < n - m) {
                textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + m)) % PRIME;
                // 處理負數哈希值
                if (textHash < 0) {
                    textHash += PRIME;
                }
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 打印結果
    public static void main(String[] args) {
        String text = "ABABCABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int position = search(text, pattern);
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 處匹配");
            System.out.println(text);
            // 打印指示匹配位置的指針
            for (int i = 0; i < position; i++) {
                System.out.print(" ");
            }
            System.out.println(pattern);
        }
    }
}

優化：使用更好的哈希函數

比如使用更復雜的哈希函數來減少衝突

public class ImprovedRabinKarp {
    private final static long PRIME1 = 1000000007; // 第一個哈希的質數
    private final static long PRIME2 = 1000000009; // 第二個哈希的質數
    
    // 使用雙哈希來減少衝突
    public static int search(String text, String pattern) {
        int m = pattern.length();
        int n = text.length();
        
        if (m > n) return -1;
        if (m == 0) return 0;
        
        // 計算哈希乘數
        long h1 = 1;
        long h2 = 1;
        for (int i = 0; i < m - 1; i++) {
            h1 = (h1 * 256) % PRIME1;
            h2 = (h2 * 256) % PRIME2;
        }
        
        // 計算模式串和第一個窗口的哈希值
        long patternHash1 = 0;
        long patternHash2 = 0;
        long textHash1 = 0;
        long textHash2 = 0;
        
        for (int i = 0; i < m; i++) {
            patternHash1 = (256 * patternHash1 + pattern.charAt(i)) % PRIME1;
            patternHash2 = (256 * patternHash2 + pattern.charAt(i)) % PRIME2;
            textHash1 = (256 * textHash1 + text.charAt(i)) % PRIME1;
            textHash2 = (256 * textHash2 + text.charAt(i)) % PRIME2;
        }
        
        // 滑動窗口，比較哈希值
        for (int i = 0; i <= n - m; i++) {
            // 兩個哈希都相等時，再進行字符比較
            if (patternHash1 == textHash1 && patternHash2 == textHash2) {
                boolean match = true;
                for (int j = 0; j < m; j++) {
                    if (text.charAt(i + j) != pattern.charAt(j)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return i; // 找到匹配
                }
            }
            
            // 計算下一個窗口的哈希值
            if (i < n - m) {
                textHash1 = (256 * (textHash1 - text.charAt(i) * h1) + text.charAt(i + m)) % PRIME1;
                textHash2 = (256 * (textHash2 - text.charAt(i) * h2) + text.charAt(i + m)) % PRIME2;
                
                // 處理負數哈希值
                if (textHash1 < 0) textHash1 += PRIME1;
                if (textHash2 < 0) textHash2 += PRIME2;
            }
        }
        
        return -1; // 未找到匹配
    }
}

優點

• 平均情況下時間複雜度為O(n+m)，接近線性時間
• 在多模式匹配場景下效率高
• 可以通過預處理模式串提高效率
• 滾動哈希計算使得算法高效移動窗口
• 實現相對簡單，原理容易理解

缺點

• 哈希衝突可能導致額外的字符比較
• 最壞情況下的時間複雜度為O(n*m)
• 哈希函數的選擇對算法性能影響很大
• 需要注意數值溢出問題
• 對於短模式串和文本串，預處理開銷可能抵消算法優勢

應用場景

1）文檔相似度檢測和抄襲檢測
2）網絡安全中的特徵碼匹配
3）多模式字符串搜索引擎
4）編譯器中的詞法分析器

擴展：Rabin-Karp指紋算法

Rabin-Karp算法的一個變種應用於文件相似度比較

public class RabinKarpFingerprint {
    private final static long PRIME = 1000000007;
    private final static int WINDOW_SIZE = 5; // 指紋窗口大小
    
    public static Set<Long> generateFingerprints(String text) {
        Set<Long> fingerprints = new HashSet<>();
        int n = text.length();
        
        if (n < WINDOW_SIZE) {
            fingerprints.add(calculateHash(text, n));
            return fingerprints;
        }
        
        // 計算第一個窗口的哈希值
        long textHash = calculateHash(text, WINDOW_SIZE);
        fingerprints.add(textHash);
        
        // 計算哈希乘數
        long h = 1;
        for (int i = 0; i < WINDOW_SIZE - 1; i++) {
            h = (h * 256) % PRIME;
        }
        
        // 滑動窗口，計算所有長度為WINDOW_SIZE的子串哈希值
        for (int i = 0; i <= n - WINDOW_SIZE - 1; i++) {
            textHash = (256 * (textHash - text.charAt(i) * h) + text.charAt(i + WINDOW_SIZE)) % PRIME;
            if (textHash < 0) {
                textHash += PRIME;
            }
            fingerprints.add(textHash);
        }
        
        return fingerprints;
    }
    
    public static double calculateSimilarity(String text1, String text2) {
        Set<Long> fingerprints1 = generateFingerprints(text1);
        Set<Long> fingerprints2 = generateFingerprints(text2);
        
        // 計算交集大小
        Set<Long> intersection = new HashSet<>(fingerprints1);
        intersection.retainAll(fingerprints2);
        
        // 計算並集大小
        Set<Long> union = new HashSet<>(fingerprints1);
        union.addAll(fingerprints2);
        
        // 傑卡德相似度係數
        return (double) intersection.size() / union.size();
    }
    
    private static long calculateHash(String str, int length) {
        long hash = 0;
        for (int i = 0; i < length; i++) {
            hash = (256 * hash + str.charAt(i)) % PRIME;
        }
        return hash;
    }
}

擴展：子字符串哈希

一些編程競賽裏也使用Rabin-Karp思想進行高效的子字符串查詢

public class SubstringHash {
    private static final long PRIME = 1000000007;
    private static final int BASE = 256;
    
    private long[] hash; // 前綴哈希值
    private long[] pow;  // BASE的冪
    private String s;    // 源字符串
    
    public SubstringHash(String s) {
        this.s = s;
        int n = s.length();
        hash = new long[n + 1];
        pow = new long[n + 1];
        
        // 預計算BASE的冪
        pow[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow[i] = (pow[i - 1] * BASE) % PRIME;
        }
        
        // 計算所有前綴的哈希值
        hash[0] = 0;
        for (int i = 0; i < n; i++) {
            hash[i + 1] = (hash[i] * BASE + s.charAt(i)) % PRIME;
        }
    }
    
    // 計算子串s[l..r]的哈希值（0-indexed）
    public long substringHash(int l, int r) {
        // 獲取s[0...r]的哈希值，減去s[0...l-1]的哈希值（需要進行適當調整）
        long result = (hash[r + 1] - (hash[l] * pow[r - l + 1]) % PRIME) % PRIME;
        if (result < 0) {
            result += PRIME;
        }
        return result;
    }
    
    // 檢查兩個子串是否相同
    public boolean areSubstringsEqual(int l1, int r1, int l2, int r2) {
        if (r1 - l1 != r2 - l2) {
            return false; // 長度不同
        }
        return substringHash(l1, r1) == substringHash(l2, r2);
    }
}

相關的 LeetCode 熱門題目

• 28. 實現 strStr()
• 187. 重複的DNA序列 - 利用Rabin-Karp滾動哈希思想解決
• 1044. 最長重複子串 - 結合二分查找和Rabin-Karp算法
• 1554. 只有一個不同字符的字符串

Rabin-Karp算法巧妙結合哈希計算和滾動窗口技術，在字符串匹配領域提供了一種高效的解決方案，特別適合多模式匹配和大規模文本處理場景。

Boyer-Moore算法

Boyer-Moore算法是一種高效的字符串匹配算法，由 Robert S. Boyer和J Strother Moore 設計於1977年。它從右向左比較字符，並利用兩個啓發式規則（壞字符規則和好後綴規則）在不匹配情況下實現較大跳躍，減少比較次數。Boyer-Moore算法在實際應用中大部分情況下比樸素算法和KMP算法更高效。

算法步驟

1. 預處理模式串，構建壞字符表和好後綴表
2. 將模式串對齊到文本串的開始位置
3. 從模式串的最右側字符開始比較，從右向左進行匹配
4. 如果發生不匹配，通過以下規則計算跳轉距離：
   • 壞字符規則：根據不匹配字符在模式串中的最右位置決定跳轉距離
   • 好後綴規則：根據已匹配部分在模式串中的重複情況決定跳轉距離
5. 選擇兩個規則中的最大跳轉距離，移動模式串
6. 重複步驟3-5，直到找到匹配或到達文本串末尾

核心特性：

• 從右向左比較：與大多數字符串匹配算法不同，從模式串的末尾開始比較
• 雙規則跳轉：利用壞字符規則和好後綴規則計算跳轉距離
• 時間複雜度：最壞情況O(m*n)，m是模式串長度，n是文本串長度；平均情況接近O(n/m)
• 空間複雜度：O(k+m)，其中k是字符集大小，m是模式串長度
• 適用範圍：特別適合長模式串和大字符集場景

基礎實現

public class BoyerMoore {
    private final int R; // 字符集大小
    private int[] badChar; // 壞字符表
    private int[] goodSuffix; // 好後綴表
    private int[] borderPos; // 邊界位置表
    private String pattern; // 模式串
    
    public BoyerMoore(String pattern) {
        this.R = 256; // ASCII字符集
        this.pattern = pattern;
        int m = pattern.length();
        
        // 初始化壞字符表
        badChar = new int[R];
        for (int c = 0; c < R; c++) {
            badChar[c] = -1; // 初始化為-1
        }
        for (int j = 0; j < m; j++) {
            badChar[pattern.charAt(j)] = j; // 記錄每個字符最右出現位置
        }
        
        // 初始化好後綴表和邊界位置表
        goodSuffix = new int[m];
        borderPos = new int[m];
        processSuffixes();
    }
    
    // 預處理好後綴表
    private void processSuffixes() {
        int m = pattern.length();
        int i = m, j = m + 1;
        borderPos[i] = j;
        
        // 計算邊界位置
        while (i > 0) {
            while (j <= m && pattern.charAt(i - 1) != pattern.charAt(j - 1)) {
                if (goodSuffix[j] == 0) {
                    goodSuffix[j] = j - i;
                }
                j = borderPos[j];
            }
            i--; j--;
            borderPos[i] = j;
        }
        
        // 計算好後綴表
        j = borderPos[0];
        for (i = 0; i <= m; i++) {
            if (goodSuffix[i] == 0) {
                goodSuffix[i] = j;
            }
            if (i == j) {
                j = borderPos[j];
            }
        }
    }
    
    // 搜索文本串中的匹配
    public int search(String text) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;
        
        int skip;
        for (int i = 0; i <= n - m; i += skip) {
            skip = 0;
            for (int j = m - 1; j >= 0; j--) {
                if (pattern.charAt(j) != text.charAt(i + j)) {
                    // 壞字符規則
                    skip = Math.max(1, j - badChar[text.charAt(i + j)]);
                    // 好後綴規則
                    if (j < m - 1) {
                        skip = Math.max(skip, goodSuffix[j + 1]);
                    }
                    break;
                }
            }
            if (skip == 0) return i; // 找到匹配
        }
        return -1; // 沒有找到匹配
    }
    
    // 測試
    public static void main(String[] args) {
        String text = "HERE IS A SIMPLE EXAMPLE";
        String pattern = "EXAMPLE";
        
        BoyerMoore bm = new BoyerMoore(pattern);
        int position = bm.search(text);
        
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 處匹配");
            System.out.println(text);
            for (int i = 0; i < position; i++) {
                System.out.print(" ");
            }
            System.out.println(pattern);
        }
    }
}

優化策略

簡化好後綴表構建

對於一些應用場景，可以只使用壞字符規則，簡化算法實現

public class SimplifiedBoyerMoore {
    private final int R; // 字符集大小
    private int[] badChar; // 壞字符表
    private String pattern; // 模式串
    
    public SimplifiedBoyerMoore(String pattern) {
        this.R = 256; // ASCII字符集
        this.pattern = pattern;
        int m = pattern.length();
        
        // 初始化壞字符表
        badChar = new int[R];
        for (int c = 0; c < R; c++) {
            badChar[c] = -1; // 初始化為-1
        }
        for (int j = 0; j < m; j++) {
            badChar[pattern.charAt(j)] = j; // 記錄每個字符最右出現位置
        }
    }
    
    // 搜索文本串中的匹配
    public int search(String text) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;
        
        int skip;
        for (int i = 0; i <= n - m; i += skip) {
            skip = 0;
            for (int j = m - 1; j >= 0; j--) {
                if (pattern.charAt(j) != text.charAt(i + j)) {
                    // 僅使用壞字符規則
                    skip = Math.max(1, j - badChar[text.charAt(i + j)]);
                    break;
                }
            }
            if (skip == 0) return i; // 找到匹配
        }
        return -1; // 沒有找到匹配
    }
}

緩存預計算結果

針對需要重複搜索同一模式串的場景，可以預計算並緩存結果

public class CachedBoyerMoore {
    private Map<String, BoyerMoore> cache = new HashMap<>();
    
    public int search(String text, String pattern) {
        // 檢查緩存中是否有預計算的Boyer-Moore對象
        BoyerMoore bm = cache.get(pattern);
        if (bm == null) {
            bm = new BoyerMoore(pattern);
            cache.put(pattern, bm);
        }
        
        return bm.search(text);
    }
}

優點

• 在實際應用中，大部分場景比KMP和樸素算法更高效
• 最好情況下可以跳過大量文本，實現亞線性時間複雜度
• 對於長模式串和大字符集特別有效
• 預處理跟模式串有關，與文本串長度無關

缺點

• 預處理複雜，特別是好後綴表的構建
• 需要額外空間存儲壞字符表和好後綴表
• 最壞情況下時間複雜度仍為O(m*n)
• 對於短模式串，預處理開銷可能抵消算法優勢
• 好後綴規則的實現較複雜，容易出錯

應用場景

1）文本編輯器的查找功能
2）網絡安全中的特徵碼匹配
3）自然語言處理中的關鍵詞檢索
4）大規模文本數據處理

擴展：Horspool算法

Horspool算法是Boyer-Moore的簡化版本，只使用壞字符規則，但是對壞字符表進行了修改

public class Horspool {
    private final int R; // 字符集大小
    private int[] badChar; // 壞字符表
    private String pattern; // 模式串
    
    public Horspool(String pattern) {
        this.R = 256; // ASCII字符集
        this.pattern = pattern;
        int m = pattern.length();
        
        // 初始化壞字符表
        badChar = new int[R];
        // 所有字符默認移動模式串長度
        for (int c = 0; c < R; c++) {
            badChar[c] = m;
        }
        // 模式串中的字符（除了最後一個）設置為對應值
        for (int j = 0; j < m - 1; j++) {
            badChar[pattern.charAt(j)] = m - 1 - j;
        }
    }
    
    // 搜索文本串中的匹配
    public int search(String text) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;
        if (m > n) return -1;
        
        int i = m - 1; // 從模式串最後一個字符對齊開始
        while (i < n) {
            int k = 0;
            while (k < m && pattern.charAt(m - 1 - k) == text.charAt(i - k)) {
                k++;
            }
            
            if (k == m) {
                return i - m + 1; // 找到匹配
            }
            
            // 使用壞字符規則移動
            i += badChar[text.charAt(i)];
        }
        
        return -1; // 沒有找到匹配
    }
}

擴展：Sunday算法

Sunday算法是另一種Boyer-Moore的變種，它關注的是文本串中模式串後面的字符

public class Sunday {
    private final int R; // 字符集大小
    private int[] shift; // 移動表
    private String pattern; // 模式串
    
    public Sunday(String pattern) {
        this.R = 256; // ASCII字符集
        this.pattern = pattern;
        int m = pattern.length();
        
        // 初始化移動表
        shift = new int[R];
        // 所有字符默認移動模式串長度+1
        for (int c = 0; c < R; c++) {
            shift[c] = m + 1;
        }
        // 模式串中的字符設置為對應值
        for (int j = 0; j < m; j++) {
            shift[pattern.charAt(j)] = m - j;
        }
    }
    
    // 搜索文本串中的匹配
    public int search(String text) {
        int n = text.length();
        int m = pattern.length();
        if (m == 0) return 0;
        if (m > n) return -1;
        
        int i = 0; // 從文本串開始位置
        while (i <= n - m) {
            int j = 0;
            while (j < m && pattern.charAt(j) == text.charAt(i + j)) {
                j++;
            }
            
            if (j == m) {
                return i; // 找到匹配
            }
            
            // 下一個位置超出文本串長度，返回-1
            if (i + m >= n) {
                return -1;
            }
            
            // 使用Sunday算法的移動規則
            i += shift[text.charAt(i + m)];
        }
        
        return -1; // 沒有找到匹配
    }
}

相關的 LeetCode 熱門題目

• 28. 實現strStr()
• 459. 重複的子字符串
• 686. 重複疊加字符串匹配
• 1392. 最長快樂前綴

KMP算法

KMP（Knuth-Morris-Pratt）算法是一種高效的字符串匹配算法，核心思想是利用已經部分匹配的信息，避免重複比較，在文本串中快速查找模式串。KMP算法特別適合處理長文本和重複性高的模式串，時間複雜度是O(m+n)，m是模式串長度，n是文本串長度。

KMP算法的關鍵在於構建一個部分匹配表（也叫失敗函數或者next數組），這個表記錄了當匹配失敗時，模式串指針應該回退到的位置，讓算法跳過已知不可能匹配的位置，提高匹配效率。

算法步驟

KMP算法主要分為兩個階段：

1. 預處理階段：計算模式串的部分匹配表（next數組）
   • 構建一個數組，記錄每個位置的最長相等前後綴長度
   • 該數組用於在匹配失敗時確定模式串指針的回退位置
2. 匹配階段：使用部分匹配表在文本串中查找模式串
   • 從左到右同時遍歷文本串和模式串
   • 當字符不匹配時，根據next數組回退模式串指針
   • 當模式串完全匹配時，記錄匹配位置並繼續查找其他匹配

核心特性：

• 線性時間複雜度：O(m+n)，其中m是模式串長度，n是文本串長度
• 高效利用歷史信息：通過預處理避免了重複比較
• 只需一次遍歷文本串：文本串指針不會回退
• 空間複雜度：O(m)，僅需存儲模式串的部分匹配表
• 適用場景：特別適合長文本和具有重複性的模式串

基礎實現

暴力解法

public class NaiveStringMatcher {
    
    /**
     * 樸素字符串匹配算法
     * @param text 文本串
     * @param pattern 模式串
     * @return 匹配成功則返回模式串在文本串中的起始位置，否則返回-1
     */
    public static int naiveSearch(String text, String pattern) {
        int n = text.length();
        int m = pattern.length();
        
        // 特殊情況處理
        if (m == 0) return 0;
        if (n < m) return -1;
        
        // 嘗試所有可能的匹配位置
        for (int i = 0; i <= n - m; i++) {
            int j;
            
            // 從當前位置開始比較模式串和文本串
            for (j = 0; j < m; j++) {
                if (text.charAt(i + j) != pattern.charAt(j)) {
                    break; // 發現不匹配字符，終止內層循環
                }
            }
            
            // 如果j等於m，説明模式串完全匹配
            if (j == m) {
                return i; // 返回匹配位置
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 使用示例
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int position = naiveSearch(text, pattern);
        
        if (position == -1) {
            System.out.println("未找到匹配");
        } else {
            System.out.println("模式串在位置 " + position + " 處匹配");
        }
    }
}

上述實現暴力枚舉所有可能的匹配位置，逐一比較文本串與模式串的每個字符，直到找到完全匹配或確定不存在匹配

KMP算法的實現

public class KMP {
    // 構建部分匹配表（next數組）
    private static int[] buildNext(String pattern) {
        int m = pattern.length();
        int[] next = new int[m];
        next[0] = 0; // 第一個字符的最長相等前後綴長度為0
        
        for (int i = 1, j = 0; i < m; i++) {
            // 當前字符不匹配，回退j
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 當前字符匹配，j向前移動
            if (pattern.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 記錄當前位置的最長相等前後綴長度
            next[i] = j;
        }
        
        return next;
    }
    
    // KMP搜索算法
    public static int kmpSearch(String text, String pattern) {
        if (pattern == null || pattern.length() == 0) {
            return 0;
        }
        
        if (text == null || text.length() < pattern.length()) {
            return -1;
        }
        
        int n = text.length();
        int m = pattern.length();
        
        // 構建next數組
        int[] next = buildNext(pattern);
        
        // 進行匹配
        for (int i = 0, j = 0; i < n; i++) {
            // 當前字符不匹配，根據next數組回退j
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 當前字符匹配，j向前移動
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 完全匹配，返回起始索引
            if (j == m) {
                return i - m + 1;
            }
        }
        
        return -1; // 未找到匹配
    }
    
    // 查找所有匹配位置
    public static List<Integer> kmpSearchAll(String text, String pattern) {
        List<Integer> positions = new ArrayList<>();
        if (pattern == null || pattern.length() == 0) {
            return positions;
        }
        
        if (text == null || text.length() < pattern.length()) {
            return positions;
        }
        
        int n = text.length();
        int m = pattern.length();
        
        // 構建next數組
        int[] next = buildNext(pattern);
        
        // 進行匹配
        for (int i = 0, j = 0; i < n; i++) {
            // 當前字符不匹配，回退j
            while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
                j = next[j - 1];
            }
            
            // 當前字符匹配，j向前移動
            if (text.charAt(i) == pattern.charAt(j)) {
                j++;
            }
            
            // 完全匹配，記錄位置並繼續匹配
            if (j == m) {
                positions.add(i - m + 1);
                // 回退j以尋找下一個匹配
                j = next[j - 1];
            }
        }
        
        return positions;
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        int pos = kmpSearch(text, pattern);
        List<Integer> allPos = kmpSearchAll(text, pattern);
        
        System.out.println("文本: " + text);
        System.out.println("模式: " + pattern);
        System.out.println("首次匹配位置: " + (pos != -1 ? pos : "未找到"));
        System.out.println("所有匹配位置: " + allPos);
        
        // 打印next數組，幫助理解
        int[] next = buildNext(pattern);
        System.out.print("next數組: ");
        for (int val : next) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

在上述代碼中：

// 當前字符不匹配，回退j
while (j > 0 && text.charAt(i) != pattern.charAt(j)) {
    j = next[j - 1];
}

是 KMP 算法的核心，在匹配失敗時根據預先計算的next數組來確定模式串指針的回退位置。

優化

優化後的 next 數組

// 優化next數組，避免匹配失敗後回退到同樣會失敗的位置
private static int[] buildOptimizedNext(String pattern) {
    int m = pattern.length();
    int[] next = new int[m];
    next[0] = 0;
    
    for (int i = 1, j = 0; i < m; i++) {
        while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        // 當前位置匹配失敗時，如果回退位置的字符與當前位置相同，則繼續回退
        if (i + 1 < m && pattern.charAt(i + 1) == pattern.charAt(j)) {
            next[i] = next[j - 1];
        } else {
            next[i] = j;
        }
    }
    
    return next;
}

預處理減少分支實現

// 預處理字符映射，減少字符比較的分支
public static int kmpSearchOptimized(String text, String pattern) {
    if (pattern == null || pattern.length() == 0) {
        return 0;
    }
    
    if (text == null || text.length() < pattern.length()) {
        return -1;
    }
    
    int n = text.length();
    int m = pattern.length();
    
    // 使用數組映射來加速字符比較（假設字符集為ASCII）
    // 為每個模式字符的每個位置創建一個狀態轉移表
    int[][] dfa = new int[256][m];
    
    // 初始化第一個字符的DFA
    dfa[pattern.charAt(0)][0] = 1;
    
    for (int X = 0, j = 1; j < m; j++) {
        // 複製匹配失敗情況下的值
        for (int c = 0; c < 256; c++) {
            dfa[c][j] = dfa[c][X];
        }
        // 設置匹配成功情況下的值
        dfa[pattern.charAt(j)][j] = j + 1;
        // 更新重啓狀態
        X = dfa[pattern.charAt(j)][X];
    }
    
    // 模式匹配
    int i, j;
    for (i = 0, j = 0; i < n && j < m; i++) {
        j = dfa[text.charAt(i)][j];
    }
    
    if (j == m) {
        return i - m; // 找到匹配
    } else {
        return -1;    // 未找到匹配
    }
}

優點

• 時間複雜度為O(m+n)，優於樸素的字符串匹配算法(暴力解法)
• 文本串只需掃描一次，不會回退
• 對於包含重複模式的字符串會高效
• 預處理模式串，可以多次用於不同的文本串
• 能快速跳過已知不會匹配的位置

缺點

• 需要額外的空間存儲next數組
• 構建next數組的邏輯較為複雜，不易理解
• 在模式串較短或無重複模式時，相比簡單算法優勢不明顯
• 實現時容易出錯，特別是處理邊界情況

應用場景

1）生物信息學中的DNA序列匹配
2）網絡入侵檢測系統中的模式匹配
3）搜索引擎的關鍵詞匹配
4）數據壓縮算法中的模式識別

擴展：多模式字符串匹配

// Aho-Corasick算法 - KMP的多模式擴展
public static class AhoCorasick {
    static class TrieNode {
        TrieNode[] children = new TrieNode[256];
        TrieNode fail;
        List<Integer> patternIndices = new ArrayList<>();
        
        public TrieNode() {
            fail = null;
        }
    }
    
    private TrieNode root;
    private String[] patterns;
    
    public AhoCorasick(String[] patterns) {
        this.patterns = patterns;
        buildTrie();
        buildFailureLinks();
    }
    
    private void buildTrie() {
        root = new TrieNode();
        
        for (int i = 0; i < patterns.length; i++) {
            String pattern = patterns[i];
            TrieNode node = root;
            
            for (char c : pattern.toCharArray()) {
                if (node.children[c] == null) {
                    node.children[c] = new TrieNode();
                }
                node = node.children[c];
            }
            
            node.patternIndices.add(i);
        }
    }
    
    private void buildFailureLinks() {
        Queue<TrieNode> queue = new LinkedList<>();
        
        // 初始化根節點的子節點
        for (int i = 0; i < 256; i++) {
            if (root.children[i] != null) {
                root.children[i].fail = root;
                queue.offer(root.children[i]);
            } else {
                root.children[i] = root;
            }
        }
        
        // BFS構建失敗鏈接
        while (!queue.isEmpty()) {
            TrieNode node = queue.poll();
            
            for (int i = 0; i < 256; i++) {
                if (node.children[i] != null) {
                    TrieNode failNode = node.fail;
                    
                    while (failNode != root && failNode.children[i] == null) {
                        failNode = failNode.fail;
                    }
                    
                    failNode = failNode.children[i];
                    node.children[i].fail = failNode;
                    
                    // 合併匹配結果
                    node.children[i].patternIndices.addAll(failNode.patternIndices);
                    
                    queue.offer(node.children[i]);
                }
            }
        }
    }
    
    public List<Pair<Integer, Integer>> search(String text) {
        List<Pair<Integer, Integer>> results = new ArrayList<>();
        TrieNode currentState = root;
        
        for (int i = 0; i < text.length(); i++) {
            char c = text.charAt(i);
            
            while (currentState != root && currentState.children[c] == null) {
                currentState = currentState.fail;
            }
            
            currentState = currentState.children[c];
            
            for (int patternIndex : currentState.patternIndices) {
                int endPos = i;
                int startPos = endPos - patterns[patternIndex].length() + 1;
                results.add(new Pair<>(patternIndex, startPos));
            }
        }
        
        return results;
    }
    
    static class Pair<K, V> {
        K first;
        V second;
        
        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }
    }
}

相關的 LeetCode 熱門題目

• 28. 找出字符串中第一個匹配項的下標 - 標準的字符串匹配問題
• 214. 最短迴文串 - 可以使用KMP算法的next數組思想解決
• 459. 重複的子字符串 - 使用KMP的next數組判斷字符串是否由重複子串構成
• 1392. 最長快樂前綴

KMP算法是字符串處理中的經典算法，用來解決字符串匹配問題，理解它對提升算法設計能力還是很有幫助的。