BF算法

首先原串与字串左端对齐，，如果第一个字符不匹配，字串向后移动逐一移动，当发现死一个第一个字符匹配后，当前位置下比较剩余字串的字符与原串是否匹配，直到全部匹配。

1
2
3
4
5
6
7
对齐:
litchicoder
coder

逐一移动 找到匹配字符:
litchicoder
      coder

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class BF {

    public static void main(String[] args) {
        int r = queryByBF("HelloWord", "Word");
        System.out.print(r == 0 ? "字符串匹配失败" : "子字符串在原串的位置：" + r);
    }

    /**
     * @param s 原字符串
     * @param t 需要匹配的子字符串位置
     */
    public static int queryByBF(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            //比较字符
            if (a[i] == b[j]) {
                i++;
                j++;
            } else {
                //i后退重新匹配
                i++;
                j = 0;
            }
        }
        if (j >= t.length()) {
            return i - t.length();
        } else {
            //匹配失败
            return 0;
        }
    }
}

KMP算法

KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称KMP算法）。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。