【学习笔记】字符串匹配_ipop字符串匹配设置

暴力匹配（BF）算法

暴力匹配（BF）算法是普通的模式匹配算法。模式匹配是模式串$P$在主串$T$中的定位运算。
BF算法的思想就是将模式串$P$的第一个字符与主串$T$的第一个字符进行匹配，若相等，则继续比较$P$的第二个字符和$T$的第二个字符；若不相等，则比较$P$的第二个字符和$T$的第一个字符，依次比较，直到得出最后的匹配结果。

Rabin-Karp（RK）算法

RK算法引入了哈希值计算。如果两个字符串的哈希值不相同，则它们肯定不相同；如果它们哈希值相同，它们不一定相同。
RK算法的思想就是将模式串$P$（长度为$k$）的哈希值与主串$T$中每一个长度为$k$的子串的哈希值相比较，只保留哈希值相同的子串进行匹配。

Knuth-Morria-Pratt（KMP）算法

KMP算法与BF算法类似，但是当某个字符失配时，并不是跳回模式串$P$的开头，主串$T$也不需要回溯，而是根据next数组存储的数值，主串$T$保持不动，模式串$P$跳到$next[j]=n$处，这样就可以跳过模式串$P$的前$n$个字符。
现有模式串“ABCDABD”，

• “A”的前缀和后缀为空集，共用长度为0；
• “AB”的前缀为[A]，后缀为[B]，共用长度为0；
• “ABC”的前缀为[A, AB]，后缀为[BC, C]，共用长度为0；
• “ABCD”的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共用长度为0；
• “ABCDA”的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共用长度为1；
• “ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共用长度为2；
• “ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共用长度为0；

因此可得部分匹配值为：

当D与空格不匹配时，前面的“ABCDAB”是匹配的，查表可知，最后一个匹配字符B对应的部分匹配值为2，因此移动位数可由下式计算：
\qquad\qquad 移动位数 = 已匹配字符数 - 对应的部分匹配值

Boyer-Moore（BM）算法

BM算法从模式串$P$的尾部开始匹配，该算法定义了两个规则：

• 坏字符规则：当主串$T$中的某个字符跟模式串$P$的某个字符不匹配时，我们称文本串中的这个失配字符为坏字符，此时模式串$P$需要向右移动，移动的位数 = 坏字符在模式串中的位置 - 坏字符在模式串中最右出现的位置。此外，如果"坏字符"不包含在模式串之中，则最右出现位置为-1。
• 好后缀规则：当字符失配时，后移位数 = 好后缀在模式串中的位置 - 好后缀在模式串上一次出现的位置，且如果好后缀在模式串中没有再次出现，则为-1。

每次后移这两个规则之中的较大值。这两个规则的移动位数，只与模式串有关，与主串无关。

1. 此时无好后缀，按坏字符规则，当前与坏字符“P”进行匹配的模式串字符“E”位于模式串第6位，坏字符“P”在模式串中最右出现的位置是第4位，因此向右移动位数 = 6 - 4 = 2，即令 主串中的当前坏字符 与 模式串中最右出现的坏字符 对齐。
   
   

2. 当“I”与“A”不匹配，此时好后缀有[“MPLE”、“PLE”、“LE”、“E”]，根据好后缀规则，所有的好后缀中，只有 位于第6位的好后缀“E” 在模式串的第0位又一次出现，因此后移位数 = 6 - 0 = 6。而根据坏字符规则，后移位数 = 2 - (-1) = 3。因此使用较大的后移位数6。
   
   
   

算法分析

• BF算法实现简单，但是效率低，不过由于不需要预处理，在字符串长度很短的情况下，优势比较明显；
• KMP算法仅当模式与主串之间存在许多“部分匹配”的情况时，才显示出其时间优越性；
• RK算法需要加上计算哈希值的时间，哈希值的计算复杂度，决定了其时间复杂度；
• BM算法考虑比较全面，包括右移时的各种情况，但它使用了两个数组，预处理时间花费比较大。

代码实现

import java.util.Arrays;

public class StringMatch {
    public static int bruteForce(String target, String pattern) {
        if (target == null || pattern == null)
            return -1;
        char[] st = target.toCharArray();
        char[] sp = pattern.toCharArray();
        int tLen = st.length, pLen = sp.length;
        if (tLen == 0 || pLen == 0 || tLen < pLen)
            return -1;

        int i = 0, j = 0;
        while (i < tLen && j < pLen) {
            if (st[i] == sp[j]) {
                i++;
                j++;
            } else {
                i -= j - 1;
                j = 0;
            }
        }
        if (j == pLen)
            return i - j;
        return -1;
    }

    public static int RK(String target, String pattern) {
        if (target == null || pattern == null)
            return -1;
        int tLen = target.length(), pLen = pattern.length();
        if (tLen == 0 || pLen == 0 || tLen < pLen)
            return -1;

        int hashCode = pattern.hashCode();
        String subStr;
        for (int i = 0; i <= tLen - pLen; i++) {
            subStr = target.substring(i, i + pLen);
            if (hashCode == subStr.hashCode() && bruteForce(subStr, pattern) == 0)
                return i;
        }
        return -1;
    }

    private static int[] badTable(char[] sp, int len) {
        int[] bad_table = new int[256]; // ASCII表中的256个字符对应的移动距离
        Arrays.fill(bad_table, -1);
        for (int i = 0; i < len - 1; i++)
            bad_table[sp[i]] = len - 1 - i;
        return bad_table;
    }

    private static int[] goodTable(char[] sp, int len) {
        int[] suffix = new int[len];
        suffix[len-1] = len;
        for (int i = len - 2, j = len - 2; i >= 0; i--) {
            j = i;
            while (j >= 0 && sp[j] == sp[len - 1 - i + j])
                j--;
            suffix[i] = i - j;
        }

        int[] good_table = new int[len];
        Arrays.fill(good_table, len);
        for (int i = len - 1, j = 0; i >= 0; i--) {
            if (suffix[i] == i + 1) {
                for (; j < len - 1 - i; j++)
                    if (good_table[j] == len)
                        good_table[j] = len - 1 - i;
            }
        }
        for (int i = 0; i <= len - 2; i++) {
            good_table[len - 1 - suffix[i]] = len - 1 - i;
        }
        return good_table;
    }

    public static int BM(String target, String pattern) {
        if (target == null || pattern == null)
            return -1;
        int tLen = target.length(), pLen = pattern.length();
        if (tLen == 0 || pLen == 0 || tLen < pLen)
            return -1;

        char[] st = target.toCharArray();
        char[] sp = pattern.toCharArray();
        int[] bad_table = badTable(sp, pLen);
        int[] good_table = goodTable(sp, pLen);

        int j, i = 0;
        while (i <= tLen - pLen) {
            j = pLen - 1;
            while (j >= 0 && st[i+j] == sp[j])
                j--;
            if (j < 0)
                return i;
            i += Math.max(good_table[j], bad_table[st[i+j]] - (pLen - 1 - j));
        }
        return -1;
    }

    private static int[] kmpNext(String pattern, int len) {
        int[] next = new int[len];
        next[0] = 0; // 已匹配字符串长度为1，部分匹配值为0
        for (int i = 1, j = 0; i < len; i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j))
                j = next[j-1];
            if (pattern.charAt(i) == pattern.charAt(j))
                j++;
            next[i] = j;
        }
        return next;
    }

    public static int KMP(String target, String pattern) {
        if (target == null || pattern == null)
            return -1;
        int tLen = target.length(), pLen = pattern.length();
        if (tLen == 0 || pLen == 0 || tLen < pLen)
            return -1;

        int[] next = kmpNext(pattern, pLen);
        for (int i = 0, j = 0; i < tLen; i++) {
            while (j > 0 && target.charAt(i) != pattern.charAt(j))
                j = next[j-1];
            if (target.charAt(i) == pattern.charAt(j))
                j++;
            if (j == pLen)
                return i - j + 1;
        }
        return -1;
    }
}

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

性能测试

在随机字符串中查找长度为$k$的模式串，时间单位为毫秒ms。

在一篇英文文章中中查找长度为$k$的模式串，时间单位为毫秒ms。

测试了RK算法耗时长的原因，substring()函数占了大部分耗时，但即使减去这部分耗时，RK算法也比不过其他三种算法， 计算哈希值的耗时 并不比 直接进行字符逐字比较的耗时短，因此耗时更长。