String-Matching-Algorithm

字符串匹配

BF算法

算法概念

BF算法（Brute-Force算法）又称暴力检索算法,是最好想到也最容易实现的算法。

算法分析

BF算法从主串S的第pos个字符开始，和模式串T的第一个字符进行比较，若相等，则继续比较后续字符；否则回溯到主串S的第pos+1个字符开始重新和模式串T进行比较。以此类推，直至模式串T中的每一个字符依次和主串S中的一个连续的字符序列相等，则称模式匹配成功，此时返回模式串T的第一个字符在主串S中的位置；否则主串中没有和模式串相等的字符序列，称模式匹配不成功。

BF算法的思想比较简单，但当在最坏情况下，算法的时间复杂度为$O(MN)$,其中M和N分别是主串和模式串的长度。这个算法的主要事件耗费在失配后的比较位置有回溯，因而比较次数过多。为降低时间复杂度可采用无回溯的算法。

RK算法

之前在讨论BF算法的时候，我们说过关于模式串长度m，和主串长度n，那么在主串中就会有n-m+1个长度为m的子串，我们只需要暴力的一一对比n-m+1个子串与模式串，就可以找出主串中与模式串匹配的子串。但是这样就会出现一个问题，在每次检查子串和模式串是否匹配的时候，需要依次对比每个字符，比较耗时，所以我们现在就需要稍微进行改造，增加哈希算法，来加快子串与模式串的匹配，所以也就产生了RK算法。

算法概念

RK算法（Robin-Karp算法）又被称为哈希检索算法，是对BF算法的进一步优化，很巧妙的使用了哈希算法，让匹配的效率有了很大的提升。

算法分析

具体的思路是通过哈希算法对主串中的n-m+1个子串分别求哈希值，然后与模式串的哈希值进行比较。如果某个子串的哈希值等于模式串，那就说明子串与模式串相匹配。因为哈希值是一个数字，数字之间比较是否相等是非常快速的，所以模式串和子串的比对的效率就提高了。在找到具有相同hash值的子串后，我们实际实现时大多会再次使用BF算法扫描一遍确认是否相同。

RK算法分为子串hash值计算和比较子串hash值两部分。对于计算字串的哈希值，我们可以设计特殊的哈希算法，只需要扫描一遍主串就能得到所以子串的哈希值，因此，这一部分的时间复杂度为O(n)。由于算法实现具有再次扫描确认结果的环节，理论上最差时间复杂度与BF算法相同也为$O(MN)$,但实际hash冲突情况并不多，期望时间复杂度为$O(M+N)$。

KMP算法

算法概念

KMP 算法是 D.E.Knuth、J,H,Morris 和 V.R.Pratt 三位神人共同提出的，称之为 Knuth-Morria-Pratt 算法，简称 KMP 算法。该算法相对于 Brute-Force（暴力）算法有比较大的改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。

算法分析

KMP算法主要分为两个部分——获得next数组和模式匹配

获得next数组

获得next数组属于对需要匹配子串进行的预处理操作，主要是通过形成“部分匹配值”来避免进行模式匹配的回溯。而这个“部分匹配值”则是指字符串前缀和后缀共有元素的长度。

如对于"ABCDABD"这个串，我以"ABCDAB"举例，它含有前缀集合[A,AB,ABC,ABCD,ABCDA]，后缀集合[BCDAB,CDAB,DAB,AB,B],共有元素AB，长度为2。

通过类似过程，对于"ABCDABD"这个串，可以获得下表
| 搜索词 | A | B | C | D | A | B | D |
| ---------- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 部分匹配值 | 0 | 0 | 0 | 0 | 1 | 2 | 0 |

而获得next数组的求解代码如下:

可以参考我的另一篇博客——datastruct_3，这篇博客有nextval数组的求解，算是对next数组的进一步优化。

void get_next(String T, int next[]) {
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length ) {
        if (j == 0 || T.ch[i] == T.ch[j]) {
            ++i, ++j;
            next[i] = j;
        } else {
            //KMP算法最经典处
            j = next[j];
        }
    }
} 

模式匹配

求出next数组后，KMP算法就很简单了，基本就是在套用公式进行移动子串即可。

移动位数=已匹配的位数-最后一个匹配字符的部分匹配值

通过套用这个公式在模式匹配时进行子串的移动，就可以避免回溯过程的发生（当然采用上文链接中实现的nextval数组还可以匹配的更快，在此不具体展开），具体KMP算法实现代码如下：

int Index_KMP(String S, String T) {
    int i = 1, j = 1;
    get_next(T, next);
    while (i <= S.length && j <= T.length) {
        if (j == 0 || S.ch[i] == T.ch[j]) {
            ++i, ++j;
        } else {
            j = next[j];
            //next数组要根据实际情况决定
        }
    }
    if (j > T.length) {
        return i - T.length;
    } else {
        return 0;
    }
}

算法复杂度

由于KMP算法没有子串回溯的过程，时间复杂度是非常优秀的$O(N)$

BM算法

BM算法是KMP算法执行效率的3~5倍，各种记事本大多Ctrl+F都采用了这种算法。

算法概念

BM算法（Boyer-Moore字符串搜索算法）是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。

算法分析

虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。

BM算法原理

BM算法定义了两个规则：

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

这样的原则理解起来比较复杂（感觉这两个规则更多是为编程服务的，对于解释原理作用不大），简而言之就是要注意两个原则即可——

1. 原字符串和子串左端对齐，从尾部向前比较。如果发现全部匹配则匹配成功
2. 在匹配失败时寻找子串是否出现原字符串中的字符，有则移动到响应位置，否则直接移动到当前整体子串的后一个位置。

完整代码实现

public static int pattern(String pattern, String target) {
    int tLen = target.length();//主串的长度
    int pLen = pattern.length();//模式串的长度

    //如果模式串比主串长，没有可比性，直接返回-1
    if (pLen > tLen) {
        return -1;
    }

    int[] bad_table = build_bad_table(pattern);// 获得坏字符数值的数组，实现看下面
    int[] good_table = build_good_table(pattern);// 获得好后缀数值的数组，实现看下面

    for (int i = pLen - 1, j; i < tLen; ) {
        System.out.println("跳跃位置：" + i);
        //这里和上面实现坏字符的时候不一样的地方，我们之前提前求出坏字符以及好后缀
        //对应的数值数组，所以，我们只要在一边循环中进行比较。还要说明的一点是，这里
        //没有使用skip记录跳过的位置，直接针对主串中移动的指针i进行移动
        for (j = pLen - 1; target.charAt(i) == pattern.charAt(j); i--, j--) {
            if (j == 0) {//指向模式串的首字符，说明匹配成功，直接返回就可以了
                System.out.println("匹配成功，位置：" + i);
                //如果你还要匹配不止一个模式串，那么这里直接跳出这个循环，并且让i++
                //因为不能直接跳过整个已经匹配的字符串，这样的话可能会丢失匹配。
                //					i++;   // 多次匹配
                //					break;
                return i;
            }
        }
        //如果出现坏字符，那么这个时候比较坏字符以及好后缀的数组，哪个大用哪个
        i += Math.max(good_table[pLen - j - 1], bad_table[target.charAt(i)]);
    }
    return -1;
}

//字符信息表
public static int[] build_bad_table(String pattern) {
    final int table_size = 256;//上面已经解释过了，字符的种类
    int[] bad_table = new int[table_size];//创建一个数组，用来记录坏字符出现时，应该跳过的字符数
    int pLen = pattern.length();//模式串的长度

    for (int i = 0; i < bad_table.length; i++) {
        bad_table[i] = pLen;
        //默认初始化全部为匹配字符串长度,因为当主串中的坏字符在模式串中没有出
        //现时，直接跳过整个模式串的长度就可以了
    }
    for (int i = 0; i < pLen - 1; i++) {
        int k = pattern.charAt(i);//记录下当前的字符ASCII码值
        //这里其实很值得思考一下，bad_table就不多说了，是根据字符的ASCII值存储
        //坏字符出现最右的位置，这在上面实现坏字符的时候也说过了。不过你仔细思考
        //一下，为什么这里存的坏字符数值，是最右的那个坏字符相对于模式串最后一个
        //字符的位置？为什么？首先你要理解i的含义，这个i不是在这里的i，而是在上面
        //那个pattern函数的循环的那个i，为了方便我们称呼为I，这个I很神奇，虽然I是
        //在主串上的指针，但是由于在循环中没有使用skip来记录，直接使用I随着j匹配
        //进行移动，也就意味着，在某种意义上，I也可以直接定位到模式串的相对位置，
        //理解了这一点，就好理解在本循环中，i的行为了。

        //其实仔细去想一想，我们分情况来思考，如果模式串的最
        //后一个字符，也就是匹配开始的第一个字符，出现了坏字符，那么这个时候，直
        //接移动这个数值，那么正好能让最右的那个字符正对坏字符。那么如果不是第一个
        //字符出现坏字符呢？这种情况你仔细想一想，这种情况也就意味着出现了好后缀的
        //情况，假设我们将最右的字符正对坏字符
        bad_table[k] = pLen - 1 - i;
    }
    return bad_table;
}

//匹配偏移表
public static int[] build_good_table(String pattern) {
    int pLen = pattern.length();//模式串长度
    int[] good_table = new int[pLen];//创建一个数组，存好后缀数值
    //用于记录最新前缀的相对位置，初始化为模式串长度，因为意思就是当前后缀字符串为空
    //要明白lastPrefixPosition 的含义
    int lastPrefixPosition = pLen;

    for (int i = pLen - 1; i >= 0; --i) {
        if (isPrefix(pattern, i + 1)) {
            //如果当前的位置存在前缀匹配，那么记录当前位置
            lastPrefixPosition = i + 1;
        }
        good_table[pLen - 1 - i] = lastPrefixPosition - i + pLen - 1;
    }

    for (int i = 0; i < pLen - 1; ++i) {
        //计算出指定位置匹配的后缀的字符串长度
        int slen = suffixLength(pattern, i);
        good_table[slen] = pLen - 1 - i + slen;
    }
    return good_table;
}

//前缀匹配
private static boolean isPrefix(String pattern, int p) {
    int patternLength = pattern.length();//模式串长度
    //这里j从模式串第一个字符开始，i从指定的字符位置开始，通过循环判断当前指定的位置p
    //之后的字符串是否匹配模式串前缀
    for (int i = p, j = 0; i < patternLength; ++i, ++j) {
        if (pattern.charAt(i) != pattern.charAt(j)) {
            return false;
        }
    }
    return true;
}

//后缀匹配
private static int suffixLength(String pattern, int p) {
    int pLen = pattern.length();
    int len = 0;
    for (int i = p, j = pLen - 1; i >= 0 && pattern.charAt(i) == pattern.charAt(j); i--, j--) {
        len += 1;
    }
    return len;
}

算法复杂度

BM算法的时间复杂度最差情况可以达到$O(MN)$,但在实际使用时多表现为$O(N)$的时间复杂度。

Sunday算法

算法概念

Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似，只不过Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

算法分析

Sunday算法原理

Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

• 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；

• 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

偏移表

在预处理中，计算大小为的偏移表。

$$
f(n)
\begin{cases}
m−max{i<m|P[i]=w}, &if\ w\ is\ in\ p[0…m-1]\
m + 1, &otherwise
\end{cases}
$$

完整代码实现

#include <iostream>
#include <cstring>

using namespace std;
#define N 10005
char a[N], b[N];
int c[30];
int la, lb;
int head;

int main() {
    cin >> a >> b;
    la = strlen(a);
    lb = strlen(b);
    //初始化匹配表
    for (int i = 0; i < lb; i++) {
        c[b[i] - 'a' + 1] = lb - i;
    }
    for (int i = 0; head < la;) {
        if (a[head + i] == b[i]) {
            i++;
            if (i == lb) {
                cout << "Yes" << endl;
                return 0;
            }
        } else {
            if (c[a[head + lb] - 'a' + 1]) {
                head += c[a[head + lb] - 'a' + 1];
            } else {
                head += lb + 2;
            }
            i = 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

算法复杂度

Sunday算法的时间复杂度最差情况可以达到$O(MN)$,但在实际使用时多表现为$O(N)$的时间复杂度。