个人中心
Erlo

字符串匹配算法

2025-12-15 10:29:28 发布  
页面报错/反馈
已收藏 点赞

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

优化：使用更好的哈希函数

比如使用更复杂的哈希函数来减少冲突

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

优点

  • 平均情况下时间复杂度为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 generateFingerprints(String text) {
        Set fingerprints = new HashSet();
        int n = text.length();
        
        if (n  fingerprints1 = generateFingerprints(text1);
        Set fingerprints2 = generateFingerprints(text2);
        
        // 计算交集大小
        Set intersection = new HashSet(fingerprints1);
        intersection.retainAll(fingerprints2);
        
        // 计算并集大小
        Set 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

扩展：子字符串哈希

一些编程竞赛里也使用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

相关的 LeetCode 热门题目

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  0) {
            while (j = 0; j--) {
                if (pattern.charAt(j) != text.charAt(i + j)) {
                    // 坏字符规则
                    skip = Math.max(1, j - badChar[text.charAt(i + j)]);
                    // 好后缀规则
                    if (j

优化策略

简化好后缀表构建

对于一些应用场景，可以只使用坏字符规则，简化算法实现

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 = 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 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  n) return -1;
        
        int i = m - 1; // 从模式串最后一个字符对齐开始
        while (i

扩展：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  n) return -1;
        
        int i = 0; // 从文本串开始位置
        while (i = n) {
                return -1;
            }
            
            // 使用Sunday算法的移动规则
            i += shift[text.charAt(i + m)];
        }
        
        return -1; // 没有找到匹配
    }
}

相关的 LeetCode 热门题目

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

上述实现暴力枚举所有可能的匹配位置，逐一比较文本串与模式串的每个字符，直到找到完全匹配或确定不存在匹配

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  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()  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 kmpSearchAll(String text, String pattern) {
        List positions = new ArrayList();
        if (pattern == null || pattern.length() == 0) {
            return positions;
        }
        
        if (text == null || text.length()  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 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  0 && pattern.charAt(i) != pattern.charAt(j)) {
            j = next[j - 1];
        }
        
        if (pattern.charAt(i) == pattern.charAt(j)) {
            j++;
        }
        
        // 当前位置匹配失败时，如果回退位置的字符与当前位置相同，则继续回退
        if (i + 1

预处理减少分支实现

// 预处理字符映射，减少字符比较的分支
public static int kmpSearchOptimized(String text, String pattern) {
    if (pattern == null || pattern.length() == 0) {
        return 0;
    }
    
    if (text == null || text.length()

优点

  • 时间复杂度为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 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  queue = new LinkedList();
        
        // 初始化根节点的子节点
        for (int i = 0; i > search(String text) {
        List> results = new ArrayList();
        TrieNode currentState = root;
        
        for (int i = 0; i (patternIndex, startPos));
            }
        }
        
        return results;
    }
    
    static class Pair {
        K first;
        V second;
        
        public Pair(K first, V second) {
            this.first = first;
            this.second = second;
        }
    }
}

相关的 LeetCode 热门题目

KMP算法是字符串处理中的经典算法，用来解决字符串匹配问题，理解它对提升算法设计能力还是很有帮助的。

本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top

登录查看全部

参与评论

昵称 登录
发布评论

评论留言

还没有评论留言，赶紧来抢楼吧~~

@2025 by 唯宠科技 蜀ICP备18000267号
浏览 2966.56 万次 点击这里给我发消息

手机查看

 返回顶部

给这篇文章打个标签吧~

棒极了 糟糕透顶 好文章 PHP JAVA JS 小程序 Python SEO MySql 确认