字符串

KMP

字符串匹配

Posted by JU on May 13, 2018

Luogu3375

#include <bits/stdc++.h>
#define pr(p) printf("%d\n",p)
const int oo=2139063143;
const int N=1010000;
const int mod=1000000007;
using namespace std;
typedef long long LL;
inline void sc (int &x)
{
    x=0; static int p; p=1; static char c; c=getchar();
    while (!isdigit(c)) { if (c=='-') p=-1; c=getchar(); }
    while ( isdigit(c)) { x=(x<<1)+(x<<3)+(c-48); c=getchar(); }
    x*=p;
}
char s[N],t[N];
int n,m,nx[N];
void init_kmp ()
{
    nx[0]=0;
    int w=0;
    for (int i=2; i<=m; i++)
    {
        while (w&&t[w+1]!=t[i]) w=nx[w];
        if (t[w+1]==t[i]) ++w;
        nx[i]=w;
    }
}
void kmp ()
{
    int w=0;
    for (int i=1; i<=n; i++)
    {
        while (w&&t[w+1]!=s[i]) w=nx[w];
        if (t[w+1]==s[i]) ++w;
        if (w==m) pr(i-m+1),w=nx[w];
    }
}
int main()
{
    //freopen (".in","r",stdin);
    //freopen (".out","w",stdout);
    scanf ("%s%s",s+1,t+1);
    n=strlen (s+1),m=strlen (t+1);
    init_kmp ();
    kmp ();
    for (int i=1; i<=m; i++)
        printf ("%d ",nx[i]);
    putchar ('\n');
    return 0;
}

主程序

每当一次暴力匹配后，假如模式串的前j个字符与主串的i~i+j-1个字符成功匹配，我们则可以从其中获得一些有用的信息。举个栗子，在模式串AABCAA……中，前6个字符成功匹配了：
YLYC DSBAABCAA QRS
　 　 　 　AABCAA……
此时记这段字符的前缀pre[]为{AABCA，AABC，AAB，AA，A}，后缀suf[]为{ABCAA,BCAA,CAA,AA,A}。容易发现，当pre[k]==suf[k]时，可以直接将模式串右移k位，从而跳过了一部分枚举。将模式串前i个字符匹配成功，i+1个失败所需要右移的位数记为next[i]。由此可以得出KMP匹配的主代码：

void kmp ()
{
    int w=0;
    for (int i=1; i<=n; i++)
    {
        while (w&&t[w+1]!=s[i]) w=nx[w];
        if (t[w+1]==s[i]) ++w;
        if (w==m) pr(i-m+1),w=nx[w];
    }
}

求next[]

因为next[]只与模式串有关，所以可以将其预处理。
当然，next[]也可以暴力求解，O(m*m)。不过当较大时，这样容易超时。实际上，有O(m)的方法。
首先，边界为next[0]=-1。假设已经求出了next[1~i-1]，要求next[i]。设k=next[i-1]，分两种情况：
1)key[k+1]==key[i]，所以直接将next往后延伸一位，next[i]=++k;
2)key[k+1]!=key[i]，此时可不能将next[i]重置，不然就变成暴力了嘛。于是可以尝试减少k，又要保持是key的前缀，即k=next[k]。栗(求next最后一位，即第二个‘D’)：
ABCDABCEABCD
ABCDABCEABCD
可以发现，在D前面接ABCDABC(k)是不行的，于是接少一点，接ABC(next[k])发现可以了。假设仍不行，则递归下去：next[ next[k] ]……

void init_kmp ()
{
    nx[0]=0;
    int w=0;
    for (int i=2; i<=m; i++)
    {
        while (w&&t[w+1]!=t[i]) w=nx[w];
        if (t[w+1]==t[i]) ++w;
        nx[i]=w;
    }
}
CC 原创文章采用CC BY-NC-SA 4.0协议进行许可，转载请注明：“转载自：KMP”
CATALOG
    FRIENDS