数据结构初见：`KMP`

今天，我们来看看这么一个数据结构KMP，下面我们来通过了解KMP的基本用法和一些典型例题来逐步了解它吧，(●ˇ∀ˇ●)

`KMP`的基本用法

像往常一样，这次我们依然通过一道题来走进KMP的世界，现在有这么一个情景，我们有两个已知大小的字符串，分别是ababa，ababacaababa

现在，有一个问题，问我们第一个字符串在第二个字符串里面出现了几次，同时输出对应的下标。在这么个情景中，我们很容易可以发现，第一个字符串可以在第二个字符串里面找到两次，同时对应的下标是0和7，

这道题大家是怎么想的呢？我在第一次想的时候，就是两个for循环，对第二个字符串进行遍历，对于每一个字符，都进行逐一匹配，如果发现了一组，那么就输出对应的下标，这种方法可以保证正确性，但是不保证速度，因此，前辈们研究出来了这么一个数据结构，可以让我们在更短的时间里面找到最优解，而由于这个方法是三个人发现的，于是就取了他们三人名字的首字母，也就是我们现在说的KMP字符串

我们先来重新看看我们第一次想的朴素算法，第一步，我们设立两个指针，一个指向第一个字符串，一个指向第二个字符串

i
ababa
j&k
ababacaababa

i和j指向的字母相同，继续匹配,直到这步

    i
ababa
k    j
ababacaababa

我们发现i和j刚好满足子串匹配，于是输出k的位置，重置i和j

i
ababa
 k&j
ababacaababa

i回到了第一位，j到了第二位，这时候，我们发现第一个就不匹配了，于是我们让k加一，重置i和j

i
ababa
  k&j
ababacaababa

我们继续匹配，直到

  i
ababa
  k j
ababacaababa

我们发现，又不匹配，于是我们让k加一，再一次重置i和j

……

这样子的话，就出现了很多的重复操作，我们无法前瞻性地看出前面是否会满足匹配，我们只是一个一个的尝试，没有得到进步，所以，KMP就可以帮我们减少这种重复操作来达到快速匹配的目的

对于每一次的不匹配，我们都是直接重置i和j，那我们的j可不可以不止进一个位置，我们可以让他进几个位置，比如说这一步

i
ababa
k   j
ababacaababa

我们已经发现了i和j是匹配的，但是我们已经发现了前面ababa中有重复的字符串，比如说a,ab,aba这些字符串就是在ababa里面是重复的，我们只要按照这种规律重新计算j在一步可以前进几步，我们就可以舍弃第二个位置，直接到第三个位置

i
ababa
  k&j
ababacaababa

虽然我们直到这一步还是错的，但是有效的减少了我们的次数，我们下一步还可以减少

i
ababa
  	k&j
ababacaababa

这两次我们都是移动了2步，因为在第一个字符串中是存在ab这么个子串的，所以我们可以移动两步，如果我们发现了aba这么个子串,我们还可以更多，所以问题又转换成我们的第一个子串的每个位置对应的可以找到至多多少个子串

第一个子串
ababa
1号位 0
2号位 0
3号位 1 a
4号位 2 ab
5号位 3 aba

对于每一次查找，我们可以发现上面的规律，在第一个字符中是永远不会有重复字符串的，之后的才可以找到，像下面这个

aaaaa
1号位 0
2号位 1 a
3号位 2 aa
4号位 3 aaa
5号位 4 aaaa

再来一个

ababacaabaa
1号位		0
2号位		0
3号位		1	a
4号位		2	ab
5号位		3	aba
6号位		0
7号位		1	a
8号位		1	a
9号位		2	ab
10号位	3	aba
11号位	1	a

没错，对于每一个位置，我们找到其最多重复字符串的方法就是比较队头和队尾，比如说第10个位置，前三个和后三个的位置是匹配的，所以最多有三个，5号位也是如此

aba baca aba	a			aba是匹配的

通过找第一个字符串的子串，我们就可以有效的减少无意义匹配的数量，这样就可以减少无意义的循环，下面给出找的代码

代码如下

#include<iostream>
using namespace std;
const int N = 1000010;
int ne[N];

int main()
{
    int n, m;char a[N], b[N];
    cin >> n >> a + 1 >> m >> b + 1;
    //由于第1个字符必定为0，于是从第2位开始
    for(int i = 2, j = 0;i <= n;i++) {
        //如果发现j > 0 同时发现有字符不匹配 那就回溯，找到记忆中的可能匹配的，减少重复，直到匹配或者无法继续回溯为止
        while(j && a[i] != a[j + 1]) j = ne[j];
        //如果发现有一对匹配的 对应的j++
        if(a[i] == a[j + 1]) j++;
        //这个位置的最大子串符号数为j
        ne[i] = j;
    }
    for(int i = 1;i <= n;i++) cout << ne[i] << ' ';
    //其他代码();
    return 0;
}

input
11 ababacaabaa
output
0 0 1 2 3 0 1 1 2 3 1

于是乎，我们就找到了所有位置上的最大重复子串个数，然后我们再用相应的方法匹配两个字符串

for(int i = 1,j = 0;i <= m;i++) 
{
    while(j && b[i] != a[j+1]) j = ne[j];
    if(b[i] == a[j+1]) j++;
    //找到匹配的
    if(j == n) 
    {
        cout << i - j << ' ';
        //回溯
        j = ne[j];
    }
}

这样子我们就可以找到所有重复的字符串了，总代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1000010;
int ne[N];

int main()
{
    char a[N], b[N];
    int n, m;
    cin >> n >> a + 1 >> m >> b + 1;
    for(int i = 2,j = 0;i <= n;i++)
    {
        while(j && a[i] != a[j+1]) j = ne[j];
        if(a[i] == a[j+1]) j++;
        ne[i] = j;
    }
    for(int i = 1,j = 0;i <= m;i++)
    {
        while(j && b[i] != a[j+1]) j = ne[j];
        if(b[i] == a[j+1]) j++;
        if(j == n) 
        {
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    return 0;
}

最后的话

这个KMP字符串可以说是我在学习数据结构中最难的那个力，学了好久都没有很懂，所以这也说明算法和数据结构的恐怖和其相对应的魅力~(￣▽￣)~*，如果想通过数据结构的话，这个算法就必须要啃下来的，加油吧，acmer！

数据结构初见：KMP

KMP的基本用法

最后的话

数据结构初见：`KMP`

`KMP`的基本用法