KMP,扩展KMP,AC自动机总结+模板

为了方便统一,本文中下标均从0开始
KMP
P3375 【模板】KMP字符串匹配
对于两个字符串S1,S2(S1>S2),求S2在S1中的出现位置
例如S1=ababa,S2=aba
在这个样例中答案就是0 2
首先考虑暴力做法,对于S1的每一个字符,我们都一该字符开始往后与S2对比.时间复杂度为$O(n^2)$
很明显这并不是我们想要的,所以考虑优化,仔细观察一下,其实我们不用每个字符都去枚举一遍
如图

我们假设图中绿色区域的字符串相等,那么当第i个字符匹配完时,对于第i+1个字符,我们不需要去枚举所有字符,因为我们可以知道,
图中绿色区域时已经匹配好了的,所以我们就只需要从绿色区域以后开始匹配就行了.
那么我们就可以设一个next数组,表示以第i个字符终点,相同的前缀和后缀的最大长度为多少
如上面的aba
那么next[0]=1,next[1]=1,next[2]=1
注意不能包括自己本身,因为这样的话存的东西就没有了意义,一直都是它本身的长度
那么在匹配的时候对于第i个字符,如果相等,那么已经匹配好的长度就加1,如果不等,就开始往回跳

我们每次就往会跳,知道目前匹配的字符与第i个字符相等,这就是匹配的过程,对于求next的过程,其实也差不多,可以看成两个S2在做匹配
code

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e6 + 5;

string p, s;
int net[N], ans[N], cnt;

int main()
{
    cin >> s >> p;
    int n = p.length(), m = s.length();
    for (int i = 1, j = 0; i < n; i++)
    {
        while (j && p[i] != p[j])
            j = net[j - 1];
        if (p[i] == p[j])
            j++;
        net[i] = j;
    }
    for (int i = 0, j = 0; i < m; i++)
    { 
        while (j && s[i] != p[j])
            j = net[j - 1];
        if (s[i] == p[j])
            j++;
        if (j == n)
        {
            cout << i - n + 2 << endl;
            j = net[j - 1];
        }
    }
    for (int i = 0; i < n; i++)
        cout << net[i] << " ";
    return 0;
}

扩展KMP
P5410 【模板】扩展 KMP（Z 函数）
之所以叫扩展KMP,肯定时因为这个东西要高级一点.S1,S2同上
扩展KMP求的东西与KMP中的next有点相似,它求的时以第i个字符为起点的前缀与S2的最大前缀长度
那么这个东西要怎么求?我们先引入一个z数组,它表示S2中以第i个字符开头的后缀与前最的最长公共长度
例如对于S1=aaaabaa,S2=aaaaa
那么z[0]=5,z[1]=4,z[2]=3,z[3]=2,z[4]=1
考虑暴力做法,对于每一个字符,同样是往后遍历一边,复杂度为$O(n^2)$
那么如何用这个z数组来优化这个算法?

我们假设字符串[L,R]是我们之前已经求出的R最大的前缀那么对于S2, 下标就为[0,R-L],那么这个时候就要分两种情况讨论了,若i>R,
那么说明我们无法利用前面已知的信息,只能暴力匹配,若i<=R,那么我们就可以知道以第i个字符为起点的前缀的初始长度应为min(R-i+1,z[i-L]).
如果说z[i-L]是大于R-i+1的,那么对于R之后的字符,我们任需暴力匹配,但总时间复杂度任为O(n).这点可以证明,在这里不过多解释
对于z数组,求法同KMP的next数组,将S2与S2自身匹配.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e7 + 5;
typedef long long ll;

char a[N], b[N];
int ex[N], z[N], l1, l2;

void zbox()
{
    int l = 0, r = 0;
    z[0] = l2;
    for (int i = 1; i < l2; i++)
    {
        if (i > r)
            z[i] = 0;
        else 
            z[i] = min(r - i + 1, z[i - l]);
        while (i + z[i] < l2 && b[i + z[i]] == b[z[i]])
            z[i]++;
        if (i + z[i] - 1 > r)
            r = i + z[i] - 1, l = i;
    }
}

void exkmp()
{
    int l = 0, r = 0;
    while (ex[0] < l1 && ex[0] < l2 && a[ex[0]] == b[ex[0]])
        ex[0]++;
    for (int i = 1; i < l1; i++)
    {
        if (i > r)
            ex[i] = 0;
        else 
            ex[i] = min(r - i + 1, z[i - l]);
        while (i + ex[i] < l1 && ex[i] < l2 && a[i + ex[i]] == b[ex[i]])
            ex[i]++;
        if (i + ex[i] - 1 > r)
            r = i + ex[i] - 1, l = i;
    }
}

int main()
{
    scanf("%s%s", &a, &b);
    l1 = strlen(a), l2 = strlen(b);
    zbox();
    exkmp();
    ll ans1 = 0, ans2 = 0;
    for (int i = 0; i < l2; i++)
        ans1 ^= (ll)(i + 1) * (z[i] + 1);
    for (int i = 0; i < l1; i++)
        ans2 ^= (ll)(i + 1) * (ex[i] + 1);
    printf("%lld\n%lld", ans1, ans2);
    return 0;
}

AC自动机
KMP保证一个字符串时为线性,那么对于多个字符串,就需要AC自动机了,注意它和自动AC机的区别,它并不能自动AC题目,虽然我以前一直以为它时这个意思.
P3808 【模板】AC自动机（简单版）
对于一个字符串,以及一堆长度小于它的模式串,求这个字符串出现了多少个模式串.
例母串为ababa,模式串为a ab aba bc
那么答案为3
AC自动机是KMP与trie树的结合
如样例,首先建trie树

其中有绿色标记的代表单词结尾
其思想其实和KMP差不多,只是改成了在树上跳而已
代码

for (int i = 0, j = 0; str[i]; i++)
{
      int t = str[i] - 'a';
      while (j && !tr[j][t])
            j = net[j];
      int p = j;
      while (p)
      {
            ans += cnt[p];
            cnt[p] = 0;
            p = net[p];
      }
}

这里可以有个优化,就是在建trie图的时候,直接记录到可以跳的位置,那么就可以省掉一层循环

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;

const int N = 1e6 + 5;
int tr[N][26], net[N], cnt[N], idx, q[N], front, tail = -1;
char str[N];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i++)
    {
        int t = str[i] - 'a';
        if (!tr[p][t])
            tr[p][t] = ++idx;
        p = tr[p][t];
    }
    cnt[p]++;
}

void build()
{
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q[++tail] = tr[0][i];
    while (front <= tail)
    {
        int t = q[front++];
        for (int i = 0; i < 26; i++)
        {
            int p = tr[t][i];
            if (!p)
                tr[t][i] = tr[net[t]][i];
            else 
            {
                net[p] = tr[net[t]][i];
                q[++tail] = p;
            }
        }
    }
}

int main()
{
    int n, ans = 0;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%s", &str);
        insert();
    }
    build();
    scanf("%s", &str);
    for (int i = 0, j = 0; str[i]; i++)
    {
        int t = str[i] - 'a';
        j = tr[j][t];
        int p = j;
        while (p)
        {
            if (cnt[p] == -1)
                break;
            ans += cnt[p];
            cnt[p] = -1;
            p = net[p];
        }
    }
    printf("%d", ans);
    return 0;
}

AC自动机的拓扑优化这里就不写了