【5】KMP学习笔记

w9095 · 2023-01-11 17:36:24 · 算法·理论

前言

WFLS 2023 寒假集训 Day1

KMP好闪，拜谢KMP！

暴力算法

单模字符串匹配算法

设 i 为主串 s（文本串）指针，j 为子串 t（模式串）指针，最开始 i,j 都从 0 开始，如果 s[i]==t[j] 那么 i++ ， j++ 。否则匹配失败（失配），则 i=i-j+1 ， j=0 。

时间复杂度： O(mn)

KMP

首先我们要思考，暴力算法慢在哪里。

最主要的问题，就是这一句话:

i=i-j+1;

有没有办法可以使主指针 i 不回溯呢？

next数组

如果匹配到 t[j] 时失配，那么前 j-1 项肯定匹配。

这时就要考虑使用模式串自身的性质了。

举个例子：

asbhguwsdwqqddwsdwsdwsr
      wsdwsr
      ^   ^
      i   j

此时在 j 处失配了，但是根据观察，我们可以把模式串挪到下面位置，从而减少运算量。

asbhguwsdwqqddwsdwsdwsr
         wsdwsr
         ^  
        i,j  

由于在模式串中的前 j-1 项已经匹配了，所以我们可以在前 j-1 项中找到一个前缀，使其与后面第 j 项之前的某一段相同，然后就可以直接跳到这一段，继续进行匹配。

这是就要引入一个概念了：最大公共前缀

其实就是上面说的 一个前缀 ，在进行KMP算法时，可以把每个 j 的最大公共前缀存进一个表中，这个表就是next数组。

例如字符串 wsdwsr 的next数组

求next数组的方法：

设现在算到了第 n 位

KMP例题

例题 1 ：

P3375 【模板】KMP字符串匹配

KMP板子题，注意匹配成功时的处理，不多赘述。

#include <bits/stdc++.h>
using namespace std;
char s[1000010],t[1000010];
int next1[1000010];
int getnext(char t[],int next[])
{
    int i=0,j=-1,res=-2;
    next[0]=-1;
    int l=strlen(t);
    while(i<l)
         {
            if(j==-1||t[i]==t[j])
               {
                i++;
                j++;
                next[i]=j;
               }
            else j=next[j];
         }
    for(int i=0;i<l;i++)
        res=max(res,next[i]);
    return res;
}

int kmp(char s[],char t[],int next[])
{
    int i=0,j=0,cnt=0;
    int ls=strlen(s),lt=strlen(t);
    while(i<ls)
          {
            if(j==-1||s[i]==t[j])
                {
                i++;
                j++;
                }
            else j=next[j];
            if(j==lt)
               {
               printf("%d\n",i-lt+1);
               j=next[j];
               cnt++;
               }
          }
    return cnt;
}

int main()
{
    scanf("%s",s);
    scanf("%s",t);
    int ans=getnext(t,next1);
    int cnt=kmp(s,t,next1);
    int l=strlen(t);
    for(int i=1;i<=l;i++)
        printf("%d ",next1[i]);
    return 0;
}

例题 2 ：

P4391 [BOI2009]Radio Transmission 无线传输

此题最大的难点在于如何求出一个周期。

我们可以求出整个字串的最大公共前缀，然后开始分类讨论：