每日算法 — 使用java实现Sunday算法：单模式字符串快速匹配与偏移表优化

算法概述

Sunday算法由Daniel M. Sunday于1990年提出，是一种高效的单模式字符串匹配算法。与KMP和Boyer-Moore相比，Sunday算法的实现更为简洁，但在实际运行中常能取得媲美甚至超越BM算法的性能。其核心思想是：在发生不匹配时，关注主串中当前对齐窗口之后的第一个字符，利用该字符在模式串中的出现位置决定滑动距离。

核心原理

Sunday算法维护一个偏移表（Shift Table），记录模式串中每个字符最后一次出现的位置（从右向左）。匹配过程中：

1. 将模式串与主串某位置对齐，从左到右逐字符比较
2. 若完全匹配，返回起始位置
3. 若发生不匹配，查看主串中模式串尾部后一个字符（称为”关键字符”）
4. 若关键字符存在于模式串中，滑动距离 = 模式串长度 – 该字符在模式串中最右出现位置
5. 若关键字符不存在于模式串中，滑动距离 = 模式串长度 + 1

这种策略使得算法在最优情况下时间复杂度接近O(n/m)，其中n为主串长度，m为模式串长度。

Java完整实现

import java.util.Arrays;

/**
 * Sunday字符串匹配算法实现
 * 特点：实现简洁，实际性能优异，适合单模式匹配场景
 */
public class SundayMatcher {

    private static final int ASCII_SIZE = 256;

    /**
     * 构建偏移表（Shift Table）
     * @param pattern 模式串
     * @return 每个字符对应的偏移量数组
     */
    private static int[] buildShiftTable(String pattern) {
        int m = pattern.length();
        int[] shift = new int[ASCII_SIZE];
        // 初始化为模式串长度 + 1，表示字符不在模式串中时滑动m+1位
        Arrays.fill(shift, m + 1);

        // 记录每个字符在模式串中最右出现位置到模式串末尾的距离
        for (int i = 0; i < m; i++) {
            char c = pattern.charAt(i);
            shift[c] = m - i;
        }
        return shift;
    }

    /**
     * Sunday字符串匹配
     * @param text 主串
     * @param pattern 模式串
     * @return 模式串在主串中的首次出现位置，未找到返回-1
     */
    public static int search(String text, String pattern) {
        if (text == null || pattern == null || pattern.isEmpty()) {
            return -1;
        }

        int n = text.length();
        int m = pattern.length();

        if (m > n) {
            return -1;
        }

        int[] shift = buildShiftTable(pattern);
        int i = 0; // 主串当前对齐位置

        while (i <= n - m) {
            int j = 0;
            // 从左到右逐字符比较
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }

            if (j == m) {
                return i; // 匹配成功
            }

            // 查看模式串尾部后的第一个字符（关键字符）
            if (i + m < n) {
                char keyChar = text.charAt(i + m);
                i += shift[keyChar];
            } else {
                break; // 已到达主串末尾
            }
        }

        return -1; // 未找到
    }

    /**
     * 查找所有匹配位置
     */
    public static java.util.List<Integer> searchAll(String text, String pattern) {
        java.util.List<Integer> results = new java.util.ArrayList<>();
        if (text == null || pattern == null || pattern.isEmpty()) {
            return results;
        }

        int n = text.length();
        int m = pattern.length();

        if (m > n) {
            return results;
        }

        int[] shift = buildShiftTable(pattern);
        int i = 0;

        while (i <= n - m) {
            int j = 0;
            while (j < m && text.charAt(i + j) == pattern.charAt(j)) {
                j++;
            }

            if (j == m) {
                results.add(i);
                i++; // 继续查找下一个（允许重叠）
            } else {
                if (i + m < n) {
                    char keyChar = text.charAt(i + m);
                    i += shift[keyChar];
                } else {
                    break;
                }
            }
        }

        return results;
    }

    public static void main(String[] args) {
        String text = "ABCDAB CABCDABCDABDE";
        String pattern = "ABCDABD";

        int pos = search(text, pattern);
        System.out.println("首次匹配位置: " + pos);

        String text2 = "AAAAA";
        String pattern2 = "AA";
        System.out.println("所有匹配位置: " + searchAll(text2, pattern2));

        // 性能测试
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 1000000; i++) {
            sb.append((char) ('A' + (i % 26)));
        }
        String largeText = sb.toString();
        String pat = "XYZABC";

        long start = System.currentTimeMillis();
        int result = search(largeText, pat);
        long end = System.currentTimeMillis();
        System.out.println("大数据搜索耗时: " + (end - start) + "ms, 结果: " + result);
    }
}

复杂度分析

应用场景

• 文本编辑器搜索：实现查找功能，代码简洁且性能稳定
• 日志过滤：在大型日志文件中快速定位关键字
• DNA序列分析：生物信息学中的模式匹配任务
• 网络包过滤：防火墙规则中的字符串匹配

Sunday算法以其简洁的实现和优异的实际性能，成为工程实践中单模式匹配的首选方案之一。