kmp

为了解决什么问题?

​ 字符串匹配问题

一些基本的定义

N, M ：字符串的长度

char s[N], p[M]：待匹配串 匹配串

eg: s[N] = “ababa”, p[M] = “aba”

判断 s[N] 中是否有p[M]这个子串，如果有，下标为多少?

解决方法

1.暴力

//可能不是很严谨，但是结构类似
// n, m 分别是待匹配串，匹配串字符串的长度
for(int i = 1; i <= n; i++) {
    bool flag = true;
    for(int j = 1; j <= m；j++) {
        if(s[i] != p[j]) {
            flag = false;
            break;
        }        
    }
}
时间复杂度：O(n*m)

2.优化->kmp

一些基本定义

前缀，后缀，部分匹配表(PMT)

前缀：除了最后一个字符以外，该字符串的全部头部组合

后缀：除了第一个字符以外，该字符串的全部尾部组合

部分匹配表：一个字符串的前缀和后缀的最长公有元素的长度

idx : 数组的下标

ne[i] : 以i为结尾的部分匹配的值，ne数组即为部分匹配表。

首先默认ne数组已知; ne的性质 ne[1]=0 ne[j] < j

ne[i] = j :含义是p[1,j]==p[i-j+1,i]i为结尾长度为j的字符串是等于从1开始长度为j的字符串

为了方便理解举一个例子

例子：

S = “ababa”

P = “aba”

P中ne[2]解释：以‘a’为结尾的部分匹配的值。

eg：“aba”的前缀为[a, ab],后缀为[a, ba]; 共有元素为1.

那么我们比较的时候就先有p[M]的aba匹配到s[N]的idx = 0的位置，而后并不同暴力做法中的将i++开始j = 1开始匹配，而是令p字符串移动j - ne[j]的长度即：i不变 j = ne[j];

a b a b a

a b a

所以我们现在需要解决两个问题

ne数组的求法以及kmp匹配

求ne数组和kmp很相似，相当于自己找自己的匹配串ne[1] = 0;下标从2开始,紧扣定义。

 #include <iostream>

using namespace std;

const int M = 1e4 + 10, N = 1e5 + 10;

int m, n;
char p[M], s[N];
int ne[M];
//

int main() {
    cin >> m >> p + 1 >> n >> s + 1;

    //求ne数组
    for(int i = 2, j = 0; i <= m; i++) {
        while(j && p[i] != p[j + 1]) j = ne[j];
        if(p[i] == p[j + 1]) j++;
        ne[i] = j;
    }

    //kmp匹配
    for(int i = 1, j = 0; i <= n; i++) {
        while(j && s[i] != p[j + 1]) j = ne[j];
        if(s[i] == p[j + 1]) j++;
        if(j == m) {
            j = ne[j]; //当匹配成功时继续往下匹配
            printf("%d ", i - m);
        }
    }

    return 0;
}
/*
Test case 
input:
5
ababa
3
aba
output:
1 3
*/
复杂度：O(n)

3.API

#include <iostream>
#include <string>
using namespace std;

int main() {
    int n, m, idx;
    string s, p;
    cin >> n >> p >> m >> s;
    idx = s.find(p);
    while(idx != std::string::npos) {
        cout << idx << ' ';
        idx = s.find(p, idx + 1);
    }
    return 0;
}
/*
Test case 
input:
5
ababa
3
aba
output:
1 3
*/
*/
复杂度：O(n)

参考：阮一峰

七月

深入讲解kmp