模式匹配

题目

给你两个字符串 str 和 substr(又叫模式串) ，请你在 str 字符串中找出 substr 字符串的第一个匹配项的下标（下标从 0 开始）。如果 substr 不是 str 的一部分，则返回 -1 。

简单匹配

int findstr(string str, string substr) {
    if (substr.empty()) return 0;
    if (substr.size() > str.size()) return -1;
    for (int i = 0; i <= str.size() - substr.size(); ++i) 
        if (str.substr(i, substr.size()) == substr) 
            return i;
    return -1;
}

KMP算法

Knuth-Morris-Pratt: 一种线性时间复杂度的匹配算法

next数组的手算方法

该算法的核心为next函数或数组的求解。

备注

这里我们采用下标为0的next数组.

我们举个例子说明：字符串aabaaab的前缀函数值依次为-1,0,1,0,1,2,2。

next[0] = -1; // 第一个字母没有前序串, 默认-1.
next[1] = 0; // a 没有真前缀和真后缀 
next[2] = 1; // aa -> a
next[3] = 0; // aab 没有
next[4] = 1; // aaba -> a
next[5] = 2; // aabaa -> aa
next[6] = 2; // aabaaa -> aa

我们就可以快速地计算出模式串在主串中的每一次出现。

为什么要计算前序串的最长前后缀?

计算最大已经匹配成功的位数.

如果当前匹配失败, 只需将模式串指针指向最长前缀的后一位, 重新匹配失败的位置. 主串指针不需回溯.

而我们采用下标为0的next数组, 前序串最大前后缀的长度就是最长前缀的后一位的下标.

C++求解next数组

前缀函数的性质:

1. next[i] <= next[i-1] + 1
2. 如果s[i] = s[next[i - 1]]那么next[i] == next[i - 1] + 1

依据这两个性质: 找到最大的j使得s[0:j-1] = s[i-j:i-1]且s[j] = s[i]

基本思路: (从下标0开始)迭代依次求解模式串每一位前串的最大公共前后缀, 尾数即为next数. 一直迭代寻找下一个jump的下标.

vector<int> getNext(string substr) {
  // next数组, 默认-1, 最后只剩下s[0]的next是-1
  vector<int> next(substr.size(), -1);
  // check是当前迭代检查的下标,jump是跳转指针指向跳转位置的下标
  int jumpTo = -1, check = 0;
  while (check < substr.size()) {
    if (jumpTo == -1 || substr[jumpTo] == substr[check])
      next[++check] = ++jumpTo;
    else
      jumpTo = next[jumpTo];
  }
  return next;
}

最大前后缀长度为什么是next的下标

一个不错的博客

使用和实现

int findstr(const string& str,const string& substr){
    vector<int> next = getNext();
    // 这个check是主串指针, j是模式串指针
    int check = 0,j = -1;
    while(i < str.size()){
        // 当没有前缀匹配或者当前匹配和前缀下一位相同时
        if(j == -1 || s[i] == substr[j]){
            ++i;
            ++j;
        }
        else j = next[j];
        if(j == substr.size()) return i - substr.size();
    }
    return -1;
}