KMP

c/c++

浏览数:45

2020-6-15

基本概念

match函数的直观理解


1.match数组记录我们在遇到失配情况时需要回到pattern的哪个位置

2.match(j)这个函数可以用文字表示成

  • 当指针指向p[j]时(不包含整个串自身的)

    • 串头开始的一段子串和一段结束于p[j]的与前字串长度相等的字串

      • 如:前述的abca和abca—>位于j=0~6
    • -1——不存在这样的子串

高效的进行build match


假设前面的match值都已经求出了,现在要求第j个和match[j-1]+1个是否匹配——是否为两个相同字串

1.相同

  • match[j]=match[j-1]+1

    • 注:这里通过利用之前的结果,优化了求最大字串的时间

2.不同

  • 不同时,一个大概的感觉是match[j]需要减小,那么,到底要减小多少呢

  • 失配时,我们找match[j-1]的值(上图紫色方块)
  • match[j-1]也有它的匹配串(上图绿色方块)

    • 注:对于更小的下标,match值已经被计算出来了

  • 这样子,就构造出了比之前小的一段字串(上图第二个紫色串)使得它与pattern最开始的一段字串相等

  • 然后,我们比较”?”处的两个字符是否相等——j和开头绿色串的下一个,也就是

    • match[match[j-1]]==?==j
  • 如果他们相等,进行1过程;不等,重新进行2过程

参考资料

KMP.pdf

数据结构,浙江大学:
https://www.icourse163.org/learn/ZJU-93001#/learn/content?type=detail&id=1214143659&cid=1217772612

模板

陈越姥姥的模板

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 2e6 + 7;
typedef int Position;
#define NotFound -1
int match[maxn];
void BuildMatch(char *pattern) {//构造match函数
    Position i, j;
    int m = strlen(pattern);//求m串长
    match[0] = -1;//第一个一定匹配不上
    for (j = 1; j < m; j++) {
        i = match[j - 1];
        while ((i >= 0) && (pattern[i + 1] != pattern[j]))
            i = match[i];//失配时,i值减小
        // 继承match[j-1]=match[match[j-1]]
        if (pattern[i + 1] == pattern[j])
            match[j] = i + 1;//算j的match值时,考虑它与j-1的关系,利用之前的match值
            //j-1比的是match[j-1],j比的是match[j-1]+1——如果匹配,匹配串的长度加1
        else match[j] = -1;
    }
}
Position KMP(char *string, char *pattern) {
    int n = strlen(string);
    int m = strlen(pattern);
    Position s, p;
    if (n < m) return NotFound;
    BuildMatch(pattern);
    s = p = 0;
    while (s < n && p < m) {//只要有一个没有扫到尾部,就继续
        if (string[s] == pattern[p]) {//都相同,两个指针都往前
            s++;
            p++;
        } else if (p > 0) p = match[p - 1] + 1;//如果不同,但是不是从第一个就不同,向右滑动match[p-1]+1
        else s++;//不同,而且又是模式串的第一个,求的串的s指针后移一位
    }
    return (p == m) ? (s - m) : NotFound;
}
char String[maxn];
char pattern[maxn];
int main() {
//    char string[] = "This is a simple example.";
//    char pattern[] = "si";
//    Position p = KMP(string, pattern);
//    if (p == NotFound) printf("Not Found.\n");
//    else {
//        printf("%s\n", string + p);
//        printf("%d\n", p);
//    }
    ll n;
    cin >> String;
    cin >> n;
    while (n--) {
        cin >> pattern;
        BuildMatch(pattern);
        Position p = KMP(String, pattern);
        if (p == NotFound) printf("Not Found\n");
        else {
            printf("%s\n", String + p);
            //这里p指的是相同子串的开始的数组下标,这样写会从同样的子串开始输出后面的所有内容
            //Input
            //abcabcabcabcacabxy
            //3
            //abcabcacab
            //cabcabcd
            //abcabcabcabcacabxyz
            //Output
            //abcabcacabxy
            //Not Found
            //Not Found
        }
    }
    return 0;
}

作者:QiuHong