Hexo
0%

KMP

发表于 更新于 分类于
学习KMP的笔记

前缀和后缀

prefix table
例如：模式串为：ababc
前缀为：（前缀和后缀都是从左向右看的）
a
ab
aba
abab
ababc
以abab为例，它的最长前缀（不能是它本身）是aba，它的最长后缀是bab，由此看见abab的三个字母的前后缀是不相同的，不符合我们的要求。于是尝试abab的两个字母的前后缀，前缀为ab，后缀为ab，现在前后缀是相同的，于是对于abab来说，它的最长公共前后缀为2。
以aba为例，它的最长公共前后缀为1，前缀为a，后缀为a。
以ab为例，它的最长公共前后缀为0。
以a为例，它的最长公共前后缀为0。

因为前缀不能是字符串本身，所以将ababc对应的最长公共前后缀（0）删掉，然后再在a的前面补上一个-1，则五个前缀，对应五个最长公共前后缀，将以上结果绘成一个前缀表：
a b a b c
-1 0 0 1 2
(注意在这个时候，模式串的编号从0开始)

求next数组

视频链接![https://www.bilibili.com/video/BV1hW411a7ys/?spm_id_from=333.788.videocard.0]
以ababca为例，它的最长公共前后缀为1，要让它变成2，那么就要在结尾的a后面再加上一个b，这就是求next数组的核心思想。也就是看模式串的（如果是从0开始）第1位是不是和当前要更新的next数组对应位置的元素相等，若相等，则最长公共前后缀要加一。
如果不匹配，则移动j的位置，就相当于将模式串不断按照next数组后移，查找可以和i位置字符匹配成功的最大公共前后缀的长度。
设当前位i的前一位的最长公共前后缀为k，则

1
2
3
4
5
设
next[i-1] = k;
判断
if(next[k] == next[i])
 next[i] = next[k]+1;

代码求next数组（这个是这个视频里up主给的代码，我不太理解，而且也非常不简洁，只是记录在这里）
这个代码实现的next数组下标从0开始，模式串下标从0开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
void prefix_table(char patter[],int prefix[],int n)
{
    prefix[0] = 0;//相当于next数组
    int len = 0;//当前最大公共前后缀长度
    int i = 1;//第0位一定为0，从第1位开始比较
    while(i<n)
    {
        if(pattern[i] == pattern[len])
        {
            len++;
            prefix[i] = len;
            i++;
        }
        else
        {
            if(len>0)
              len = prefix[len-1];
            else//避免在此陷入死循环，当len = 0时就直接赋值
              {
                  prefix[i] = len;
                  i++;
              }
        }
    }
}
void move_prefix_table(int prefix[],int n)
{
    int i;
    for(i = n-1;i>0;i--)
    {
        prefix[i] = prefix[i-1];
    }
    prefix[0] = -1;
}

next求解精简版
这个代码实现里面next数组下标从1开始，模式串下标从1开始,所以在存储字符串的时候要注意一下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void get_next(char pattern[], int next[], int n)
{
    int i = 1;
    next[1] = 0;
    int j = 0;
    while (i <= n)
    {
        if (j == 0 || pattern[j] == pattern[i])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];//i不变，j后退，重新匹配,相当于将字符串移动到next[j]的位置看能不能匹配上，这样就少匹配了1~next[j]这些位置的字符，因为由最大公共前后缀可得，他们是匹配的。
        }
    }
}

用next数组进行搜索

如果next数组和模式串的下标从0开始，那么如果next数组值为-1，则

1
2
3
4
5
6
j = next[j];
if(j == -1)
{
    i++;
    j++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void kmp_search(char txt[],char pattern)
{
    int n = strlen(pattern);
    int m = strlen(text);
    int*next = new int[n];
    get_next(pattern,next,n);
    int i = 1;
    int j = 1;

    //text[i]     len(text) = m
    //pattern[j]  len(pattern) = n
    while(i<m)
    {
        if(j == n&&text[i] == pattern[j])
        {
            cout<<i-j<<endl;//匹配成功的位置
            j = next[j];//继续向后匹配，看后面还有没有和模式串匹配的位置
        }
        if(text[i] == pattern[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];
        }
    }
}

求nextval数组

这个很像是并查集里面的路径压缩，和求next数组的方法大同小异。

1
2
3
4
5
6
7
8
9
10
11
12
void get_nextval(char pattern[], int &nextval[],int n)
{
     i= 1; nextval[1] = 0; j = 0;
     while( i<n ){
          if(j==0 || pattern[i] == pattern[j]){
                ++i; ++j;
                if(pattern[i] != pattern[j]) nextval[i] = j;//如果j == 0，则nextval[0] = next[0],和next求法完全相同
                else  nextval[i] = nextval[j];//更新nextval数组
          }
          else  j = nextval[j];//在pattern中查找pattern[j]的最长公共前后缀
     }
}