子字符串查找算法：

• 暴力子字符串查找算法
• KMP 算法
• RM 算法

术语：

• 文本：完整的字符串
• 模式字符串：需要在文本中查找的子串

暴力子字符串查找算法

性能：

• 在极端情况下（存在很多重复的字符），时间复杂度是 O(MN)
• 一般情况下（不需要完整地比对模式串），时间复杂度是 O(M + N)

思路：枚举出文本中的所有和模式串长度相等的子串进行对比

算法实现1：

public class BruteForce1 {
    public static int search(String txt, String pattern) {
       int n = txt.length();
       int m = pattern.length();
        for (int i = 0; i <= n - m; i++) {
            int j;
            for (j = 0; j < m; j++) {
                if (pattern.charAt(j) != txt.charAt(j + i)) {
                    break;
                }
            }
            if (j == m) {
                return i;
            }
        }
        return -1;
    }
}

测试：

class BruteForce1Test {
    @Test
    void search() {
        Assertions.assertEquals(0, BruteForce1.search("Hello World", "Hello"));
        Assertions.assertEquals(6, BruteForce1.search("Hello World", "World"));
        Assertions.assertEquals(-1, BruteForce1.search("Hello World", "Hi"));
    }
}

思路：枚举文本的每个和模式串长度相同的子串，对比失败时回退指针 i, j

算法实现2：

public class BruteForce2 {
    public static int search(String txt, String pattern) {
        int n = txt.length();
        int m = pattern.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            if (pattern.charAt(j) == txt.charAt(i)) {
                j++;
            } else {
                i -= j;
                j = 0;
            }
        }
        if (j == m) {
            return i - m;
        }
        return -1;
    }
}

测试：

class BruteForce2Test {
    @Test
    void search() {
        Assertions.assertEquals(0, BruteForce2.search("Hello World", "Hello"));
        Assertions.assertEquals(6, BruteForce2.search("Hello World", "World"));
        Assertions.assertEquals(-1, BruteForce2.search("Hello World", "Hi"));
    }
}

KMP 算法

本节重点：

• DFA 如何使用
• DFA 如何构造

全称：Knuth-Morris-Pratt 子字符串查找算法（三位发明者的名字）

基本思想：利用已经比较过的字符信息，实现在匹配失败时，总是将 j 设置为某个值使 i 不回退

可能性：当匹配失败时，可以将模式串向右移动来避免指针 i 回退

文本串：AABAABAAAB
模式串：AABAAA 
    ->    AABAAA

实现：对模式串进行预处理，构造 DFA（确定有限状态自动机），在遍历文本串的字符时，可以从 DFA 得到下一个 j 的值，即状态

DFA: dfa[txt.chatAt(i)][j] 的值是和文本串的下一个字符 txt.chatAt(i+1) 比较的 j 值

算法实现：

public class KMP {
    private static final int R = 256; // 字符集大小
    private String pattern;
    private int m;
    private int[][] dfa;

    /**
     * 根据模式串构造确定有限状态自动机 DFA
     * */
    public KMP(String pattern) {
        this.pattern = pattern;
        this.m = pattern.length();
        dfa = new int[R][m];
        // 初始化第一列
        dfa[pattern.charAt(0)][0] = 1;
        // 初始化其他的列，从第二列开始
        // 当 txt[i..i+j] 匹配失败时，从 txt[i+1] 开始匹配，
        // 这里可以想象成DFA正在处理第 2 个字符的匹配情况
        // X 记录重启状态
        for (int j = 1, X = 0; j < m; j++) {
            for (int c = 0; c < R; c++) {
                dfa[c][j] = dfa[X][j]; // 匹配失败，将 dfa[][X] 复制到 dfa[][j]
            }
            dfa[pattern.charAt(j)][j] = j + 1; // 匹配成功，将 dfa[pattern.charAt(j)][j] 设置成 j + 1
            X = dfa[pattern.charAt(j)][X]; // 更新 X，即从 txt[i+1] 开始匹配或者说在构建自动的同时也在使用自动机
        }
    }

    /**
     * 在文本串中查找子串
     * 将文本串的字符逐个放到 DFA 中，直到 DFA 达到终止状态或文本串结束
     * */
    public int search(String txt) {
        int n = txt.length();
        int i, j;
        for (i = 0, j = 0; i < n && j < m; i++) {
            j = dfa[txt.charAt(i)][j];
        }
        if (j == m) {
            return i - m;
        }
        return -1;
    }
}

测试：

class KMPTest {
    @Test
    void search() {
        KMP kmp = new KMP("Hello");
        Assertions.assertEquals(0, kmp.search("Hello World"));
        Assertions.assertEquals(4, kmp.search("Say Hello"));
        Assertions.assertEquals(-1, kmp.search("hello world"));
    }
}

应用场景：

• 文本串和模式串的重复性很高
• 文本串是长度不确定的输入流