子字符串查找（1）

一、定义

本文主要介绍子字符串查找的各类常用算法，如朴素匹配算法（暴力查找）、KMP算法、BM算法等。各类匹配算法的比较见下图：

1-1 各类字符串匹配算法比较

可以看到，对于子字符串查找，最佳性能基本是和文本长度N成正比：

1. 暴力查找算法实现简单，且在一般情况下都能工作良好，但是具体与文本规律有关，不能保证性能。
2. KMP算法能够保证线性级别的性能，且文本指针不需要回退，需要额外的内存空间。
3. BM算法一般都是亚线性级别，其性能通常要比KMP算法好，需要额外的内存空间。
4. RK算法基于散列值的计算，一般不需要回退文本指针，但是存在冲突的可能，其性能也是线性级别。

二、暴力查找算法

2.1 定义

暴力查找算法（brute force，也称为朴素匹配算法），其思路就是，用指针i标识正在匹配的文本字符，指针j标识正在匹配的模式字符串：

• 如果当前字符匹配成功（即txt[i] == ptn[j]），则i++，j++，继续匹配下一个字符；
• 如果失配（即txt[i]! = ptn[j]），则回溯指针i（i = i - j + 1），j = 0，即每次匹配失败时，i回溯，j重置为0。

2-1 暴力查找算法示例

2.2 实现

/**
 * 基于回退的暴力查找子字符串
 * @param pat 模式字符串
 * @param txt 文本
 */
public static int search2(String pat, String txt) {
    int m = pat.length();
    int n = txt.length();
    int i, j;    //指针i跟踪文本，指针j跟踪模式字符串
    while(i < n && j < m) {
        if (txt.charAt(i) == pat.charAt(j)) {
            i++;
            j++;
        }
        else {
            i = i-j+1;
            j = 0;
        }
    }
    if (j == m) return i - j;     // found
    else        return -1;        // not found
}

2.3 性能分析

• 时间复杂度：
  最坏情况：O(MN)
  平均情况：O(M+N)
  其中 M:模式字符串长度 , N:文本长度