kmp

模板KMP

\(KMP\)简单的来是用一个串在另一个串中匹配

那么对于这样一个模板我们可以怎么处理呢?

假象现在我们在进行暴力匹配，此时情况如下: \[ s1="abcabc...."\\ s2="abcabb".... \] 可以看见现在的\(s2\)的最后一个\(b\)对齐的是\(s1\)的\(c\)

简单地说现在的\(b\)就是一个失配点

也就是说现在我们需要重新匹配

如果再从头开始的匹配的话显然有些浪费时间了

于是我们似乎可以就寻找上一个失配点的位置即\(……b\)的位置

于是我们找到了\(ab\)，也就是\(s2\)的开头的两个字符，然后继续这样匹配下去就可以了

#include <cstdio>
#include <cstring>

const int Maxn = 1e6 + 5;
char A[Maxn], B[Maxn];
int Last, LOA, LOB, KMP[Maxn];//这个KMP数组就是记录上一个失配点的位置
//后面的代码就非常的浅显易懂了
int main()
{
    scanf("%s %s", A + 1, B + 1);
    LOA = strlen(A + 1), LOB = strlen(B + 1);
    for (int i = 2; i <= LOB; ++i)
    {
        while (Last && B[i] != B[Last + 1]) Last = KMP[Last];
        if (B[Last + 1] == B[i]) ++Last;
        KMP[i] = Last;
    }
    Last = 0;
    for (int i = 1; i <= LOA; ++i)
    {
        while (Last && A[i] != B[Last + 1]) Last = KMP[Last];
        if (B[Last + 1] == A[i]) ++Last;
        if (Last == LOB)
        {
            printf("%d\n", i - LOB + 1);
            Last = KMP[Last];
        }
    }
    for (int i = 1; i <= LOB; ++i) printf("%d ", KMP[i]);
}