Java 實作 Sunday 字串搜尋演算法：原理、完整程式碼與效能比較

Sunday 演算法是 Boyer-Moore 的改良版，屬於「壞字符啟發式」家族。核心差異：BM 參考「失配位置的字符」，Sunday 參考「模式串對齊區間後的下一個字符」決定位移量。平均效能優於 BM 3-5 倍，實作更簡潔。本文提供完整 Java 實作並對比朴素搜尋。

演算法核心邏輯

1. 預處理：建立模式串 pattern 中每個字符 最右出現位置 的映射表 Map
2. 匹配嘗試：從文本 text 當前位置 pos 開始逐字符比對
3. 失配處理：
   • 取「對齊區間後的字符」c = text[pos + pattern.length()]
   • 若 c 在模式串中：位移至 c 在模式串 最右 位置對齊
   • 若 c 不在模式串：直接跳過整個模式串長度 + 1
4. 重複直到找到所有匹配或文本結束

完整實作程式碼

import java.util.*;

public class SundaySearch {
    private final String text;
    private final String pattern;
    private int pos = 0;
    private final List matches = new ArrayList<>();
    private final Map lastOccurrence = new HashMap<>();

    public SundaySearch(String text, String pattern) {
        this.text = text;
        this.pattern = pattern;
        buildLastOccurrenceMap();
    }

    private void buildLastOccurrenceMap() {
        for (int i = 0; i < pattern.length(); i++) {
            lastOccurrence.put(pattern.charAt(i), i); // 保留最右位置
        }
    }

    /** 從指定位置嘗試匹配 */
    private boolean matchAt(int pos) {
        if (pos + pattern.length() > text.length()) return false;
        for (int i = 0; i < pattern.length(); i++) {
            if (text.charAt(pos + i) != pattern.charAt(i)) return false;
        }
        return true;
    }

    /** 朴素搜尋：每次位移 1 (基準比較) */
    public List naiveSearch() {
        pos = 0; matches.clear();
        while (pos + pattern.length() <= text.length()) {
            if (matchAt(pos)) matches.add(pos);
            pos++;
        }
        return matches;
    }

    /** Sunday 搜尋 */
    public List sundaySearch() {
        pos = 0; matches.clear();
        while (pos + pattern.length() <= text.length()) {
            if (matchAt(pos)) {
                matches.add(pos);
                pos++; // 找到後移 1 繼續找下一個
            } else {
                int nextCharPos = pos + pattern.length();
                if (nextCharPos >= text.length()) break; // 越界結束

                char nextChar = text.charAt(nextCharPos);
                Integer lastPos = lastOccurrence.get(nextChar);
                if (lastPos == null) {
                    pos += pattern.length() + 1; // 字符不在模式串，大跳躍
                } else {
                    pos += pattern.length() - lastPos; // 對齊最右出現位置
                }
            }
        }
        return matches;
    }

    // 測試主程式
    public static void main(String[] args) {
        String text = "hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsffwerwrewrerwerwersdf2666sdflsdfk";
        String pattern = "adf";
        SundaySearch searcher = new SundaySearch(text, pattern);

        long t1 = System.nanoTime();
        System.out.println("Naive: " + searcher.naiveSearch() + " time: " + (System.nanoTime() - t1) + "ns");

        long t2 = System.nanoTime();
        System.out.println("Sunday: " + searcher.sundaySearch() + " time: " + (System.nanoTime() - t2) + "ns");
    }
}

關鍵程式碼解析

效能特性分析

• 最佳情況：文本中無模式串字符，每次跳躍 m+1，時間 O(n/m)
• 最壞情況：如 text="aaaaa...", pattern="aaab"，退化為 O(n*m)
• 平均情況：顯著優於朴素搜尋，接近 O(n)
• 空間複雜度：O(σ) σ=字符集大小 (Map 儲存)

對比總結

實務建議

• Java 內建 String.indexOf() (JDK 9+ 使用 Two-Way 演算法) 已高度優化，一般情況優先使用內建方法
• 需自訂比較邏輯 (如忽略大小寫、Unicode 正規化) 或教學/面試場景 → 手寫 Sunday
• 大規模文本搜尋 (GB 級) → 考慮索引結構 (倒排索引、Suffix Array、Lucene/Elasticsearch)

Sunday 演算法以簡潔實作換取優異平均效能，是字串搜尋演算法教學與輕量級工具開發的優選。