Java实现Sunday字符串匹配算法详解与代码示例

算法核心原理

Sunday算法的思想与Boyer-Moore (BM) 算法中的坏字符思想类似，但判断位置不同。BM算法通常在匹配失败时检查当前不匹配的字符，而Sunday算法在发现匹配失败时，会查看目标文本中位于“当前模式串部分”之后紧接着的那个字符（即偏移量+模式串长度+1处的字符）。

具体操作逻辑如下：

1. 检查关键字符：定位到文本中当前位置加上模式串长度后的下一个字符（称为K位置）。
2. 存在该字符：如果K位置的字符在模式串中存在，则将模式串移动到使该字符与模式串中对应的字符对齐的位置。
3. 不存在该字符：如果K位置的字符不在模式串中，则直接将整个模式串向后移动，让模式串的开头与K位置对齐。

重复上述过程，直到找到匹配子串或文本遍历完毕。

Java实现步骤

第1步：初始化数据结构

为了提高查询效率，我们需要预处理模式串，构建一个映射表。记录模式串中每个字符最后出现的位置索引。

private Map<Character, Integer> map = new HashMap<Character, Integer>;

private void initMap() {
    for (int i = 0; i < pattern.length(); i++) {
        this.map.put(pattern.charAt(i), i);
    }
}

第2步：执行Sunday匹配逻辑

主匹配逻辑采用递归方式实现。首先检查从当前位置是否完全匹配。若匹配失败，则根据上述原理计算新的偏移量：

• 未越界且字符不存在于模式串：偏移量增加 pattern.length()，跳过尽可能多的无意义区间。
• 字符存在于模式串：偏移量增加 pattern.length() - map.get(text.charAt(currentPos + pattern.length()))，实现对齐。
• 边界情况处理：若即将越界，则仅前进一位以确保不会遗漏可能的重叠匹配。

第3步：逐位普通匹配对照

为了验证Sunday算法的效率优势，同时实现了一个基础的每次移动一位的递归匹配方法作为对照组。当发生不匹配时，仅将位置指针加1继续尝试。

完整代码示例

以下为包含Sunday算法与普通匹配算法的完整Java实现类，可直接运行测试。

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * Sunday字符串匹配算法实现
 */
public class SundySearch {
    String text = null;
    String pattern = null;
    int currentPos = 0;

    /** 匹配后的子串第一个字符位置列表 */
    List<Integer> matchedPosList = new LinkedList<>();
    
    /** 存储Pattern中每个字符最后一次出现的位置 */
    Map<Character, Integer> map = new HashMap<>();

    public SundySearch(String text, String pattern) {
        this.text = text;
        this.pattern = pattern;
        this.initMap();
    }

    private void initMap() {
        for (int i = 0; i < pattern.length(); i++) {
            this.map.put(pattern.charAt(i), i);
        }
    }

    /** 普通逐位匹配 */
    public List<Integer> normalMatch() {
        if (!matchFromSpecialPos(currentPos)) {
            currentPos += 1;
            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }
            normalMatch();
        } else {
            matchedPosList.add(currentPos);
            currentPos += 1;
            normalMatch();
        }
        return matchedPosList;
    }

    /** Sunday匹配 */
    public List<Integer> sundayMatch() {
        if (!matchFromSpecialPos(currentPos)) {
            // 关键点：检查 currentPos + pattern.length() + 1 处的字符
            if ((currentPos + pattern.length() + 1) < text.length()
                    && !map.containsKey(text.charAt(currentPos + pattern.length()))) {
                // 字符不存在，直接跳过整个模式串长度
                currentPos += pattern.length();
            } else {
                // 字符存在或越界处理
                if ((currentPos + pattern.length()) >= text.length()) {
                     // 防止越界访问，实际逻辑需结合具体实现调整
                     currentPos += 1;
                } else {
                    int shift = pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
                    currentPos += shift;
                }
            }

            if ((text.length() - currentPos) < pattern.length()) {
                return matchedPosList;
            }
            sundayMatch();
        } else {
            matchedPosList.add(currentPos);
            currentPos += 1;
            sundayMatch();
        }
        return matchedPosList;
    }

    /** 辅助方法：检查指定位置开始是否匹配 */
    public boolean matchFromSpecialPos(int pos) {
        if ((text.length()-pos) < pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            if (text.charAt(pos + i) == pattern.charAt(i)) {
                if (i == (pattern.length()-1)) {
                    return true;
                }
                continue;
            } else {
                break;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        SundySearch sundySearch = new SundySearch("hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");

        long begin = System.nanoTime();
        System.out.println("NormalMatch:" + sundySearch.normalMatch());
        System.out.println("NormalTime:" + (System.nanoTime() - begin));

        begin = System.nanoTime();
        System.out.println("SundayMatch:" + sundySearch.sundayMatch());
        System.out.println("SundayTime:" + (System.nanoTime() - begin));
    }
}

结果与分析

通过 main 函数中的测试案例，我们可以直观看到两种算法的执行时间。由于使用了纳秒级计时器 System.nanoTime()，在较短的字符串下差距可能不明显，但在长文本或特定模式串（如大量非匹配字符连续出现）的情况下，Sunday算法因跳跃式移动，效率显著高于逐位比较的普通匹配，通常比BM算法也有不错的表现。

以上就是Java实现Sunday字符串匹配算法的详细内容，更多关于Java算法的资料请关注本站其它相关文章！