@dxbdly 2021-03-03T14:46:52.000000Z 字数 7632 阅读 144

G2020 19寒假集训Day3

信息学——19寒假集训

G2020 19寒假集训Day3
- 一.KMP
- 二. AC自动机

今天是G2020寒假集训Day3，主要讲字符串中的KMP，AC自动机。

一.KMP

$KMP$ 算法是用来求字符串匹配问题的重要方法。

首先介绍两个定义：

文本串：即主串，将要被模式串匹配。
模式串：即子串，将要匹配文本串。

我们先看道题：

算法分析：

$1.$ 暴力

用两个指针 $l1$ , $l2$ 分别指向文本串和模式串将要匹配的字符。

如果两个字符匹配成功，则 $l1++,l2++$ 。

如果两个字符失配，则将 $l2=1,l1=l1-l2+1$

过程如下图：

时间复杂度 $O(NM)$ 需要优化

$2.$ KMP :

思考：暴力算法的冗余在哪？

观察暴力算法，我们容易看出，当字符串失配时：

我们会让 $l2=1,l1=2$ :

那么我们会发现

由于模式串的前缀ab匹配成功.
所以当$l1=2,l1=3$时不可能匹配成功，这时可以直接跳过。

所以说

我们在两字符串失配时会将很多有效信息遗漏，从而造成冗余

而KMP算法就是运用这些信息进行优化。

$1^o$ KMP算法思想

刚刚说过了，KMP算法就是利用失配时的信息进行优化。

还是用前面的图：

他在两字符串失配时，不动文本串指针 $l1$ ,将模式串指针 $l2$ 向前移动到特定位置上，继续匹配。

下面定义 $next$ 数组：

next[i]表示模式串0~(i-1)的子串中前缀与后缀相等的最大长度。

那么我们如果得到了 $next$ 数组

即可在失配时令 $l2=next[l2]$ ,由于前缀等于后缀的原因，中间跨过的那一段一定不能匹配，可以保证正确性。

那么如果得到了 $next$ 数组我们就可以将算法有效优化。

$2^o$ next数组的求法

仔细观察next数组的定义，你会发现其中有这样一段：

前缀与后缀相等的最大长度。

前缀与后缀相等？

那是不是就是用 $0$ ~ $(i-1)$ 的模式串匹配 $0$ ~ $i$ 的模式串！

所以说我们只要将模式串自己匹配自己就可以处理出next数组。

$3^o$ KMP的时间复杂度

我们采用势能法分析。

假设模式串长度为m，文本串长度为n。
则模式串指针l2每右移一位增加1势能，且文本串指针l1移动到末尾时算法结束。
那么如果但前匹配上了，则文本串指针l1向后移动1位，且增加1势能。
如果没配上则减少x势能，文本串指针l1先后移动x位。
那么势能最多存m，指针l1最多移动n下。
所以时间复杂度为O(n+m).

$4^o$ AC代码

// The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
string s1,s2;
int len1,len2;
int nex[1000005];
inline void get_nex()
{
    int k1=0,k2;
    nex[0]=k2=-1;
    while (k1<len2)
          {
          if (k2==-1||s2[k1]==s2[k2])
             nex[++k1]=++k2;
          else
             k2=nex[k2];
          }
}
inline void KMP()
{
    int k1=0,k2=0;
    while (k1<len1)
          {
          if (k2==-1||s1[k1]==s2[k2])
             k1++,k2++;
          else
             k2=nex[k2];
          if (k2==len2)
             printf("%d\n",k1-k2+1),k2=nex[k2];
          }
}
int main(){
    cin>>s1>>s2;
    len1=s1.size(),len2=s2.size();
    get_nex();
    KMP();
    for (register int i=1;i<=len2;++i)
        printf("%d ",nex[i]);
    return 0;
}

3. 例题UVA1328 Period

样例输入：
3
aaa
12
aabaabaabaab
0
样例输出：
Test case #1
2 2
3 3
Test case #2
2 2
6 2
9 3
12 4

题解：

此题重点在于如何求一个字符串是否为周期串，以及周期的周长

观察KMP算法，我们会发现：

如果字符串是一个周期串，且他的长度为n

则一定满足 $n|(n-next[n])$ ，并且此时周期长度为 $n-next[n]$

PS：其中 $next[]$ 为KMP所处理的失配数组

所以我们只需预处理出 $next$ 数组，然后 $O(1)$ 对于n个前缀处理，总时间复杂度 $O(n)$ ，可过！

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x;
}
char s[2000005];
int len,t;
int nex[2000005];
inline void get_nex()
{
    int k1=0,k2;
    nex[0]=k2=-1;
    while (k1<len)
          {
          if (k2==-1||s[k1]==s[k2])
             nex[++k1]=++k2;
          else
             k2=nex[k2];
          }
}
int main(){
    while (len=read())  
          {
          scanf("%s",s);
          get_nex();
          printf("Test case #%d\n",++t);
          for (register int i=2;i<=len;++i)
              if (nex[i]>0&&i%(i-nex[i])==0)
                 printf("%d %d\n",i,i/(i-nex[i]));
          printf("\n");
          }
    return 0;
}

二. AC自动机

图片引用自博客

前置芝士点：Trie树，不会请自行百度(简单)

1. 定义

自动机：给你当前位置与一个操作字符，则可以找到唯一确定的下一位置
AC自动机：AC自动机其实就是在Trie树上做KMP。
fail数组：可理解为KMP中的next数组

$AC$ 自动机用于处理多模式串匹配问题，此算法将 $Trie$ 树与 $KMP$ 结合在一起，完美的解决了这类问题。

有了 $KMP$ 的基础，学习AC自动机显得简单很多。

2.建立AC自动机(fail数组的求法）

假设模式串： $"ash","shex","bcd","sha"$

匹配串： $"ashf"$

首先，我们将所有模式串建成一颗Trie树（不会请自行百度）

然后，考虑假如我们在匹配时失配了怎么办

采用 $KMP$ 思路，在失配时，跳到 $fail$ 指针所指向的地方，且当前模式串后缀与新模式串前缀相同，然后继续往下寻找。

与 $KMP$ 不同的是， $fail$ 数组一般由BFS的方式来建立。

首先，两个特判：

根节点的fail值就是本身。
根节点所有儿子的fail值是根。

然后一层一层往下递推，分两种情况讨论：

若：当前儿子未在 $Trie$ 树上出现，则将 $fail$ 值为根。

如下图节点 $a$

若：当前儿子在 $Trie$ 树上出现

我们将他的file指针指向
(他父亲fail指针所指向的节点的)(与他相同的)儿子节点

如下图节点 $s$ ：

以此类推，将 $fail$ 数组完全求出后是这样子滴：

到此为止，我们就成功的将 $AC$ 自动机建立完成，并且求出了最重要的 $fail$ 数组。

3.匹配操作

根据自动机的定义，我们可以将文本串看作操作指令

那么 $fail$ 边所对连接的点就是下一状态

我们只需要不断地顺着 $fail$ 边跳即可。

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
char s[1000005];
int trie[1000005][30],cnt,word[1000005];
int fail[1000005],ans;
inline void add()
{
    int root=0,len=strlen(s);
    for (register int i=0;i<len;++i)
        {
        int x=s[i]-'a'+1;
        if (!trie[root][x])
           trie[root][x]=++cnt;
        root=trie[root][x];
        }
    word[root]++;
}
inline void get_fail()
{
    queue <int> q;
    for (register int i=1;i<=26;++i)
        if (trie[0][i])
           fail[trie[0][i]]=0,q.push(trie[0][i]);
    while (!q.empty())
          {
          int x=q.front();
          q.pop();
          for (register int i=1;i<=26;++i)
              {
              if (trie[x][i])
                 fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
              else
                 trie[x][i]=trie[fail[x]][i];
              }
          }
}
inline void query()
{
    int len=strlen(s),now=0;
    for (register int i=0;i<len;++i)
        {
        now=trie[now][s[i]-'a'+1];
        for (register int j=now;j&&word[j]!=-1;j=fail[j])
            ans+=word[j],word[j]=-1;
        }
    printf("%d",ans);
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        scanf("%s",s),add();
    get_fail();
    scanf("%s",s);
    query();
    return 0;
}

4. 例题

$1^o$ P3796【模板】AC自动机（加强版）

题解：

此题要求我们输出那些模式串在文本串中出现次数最多
我们只需要在建Trie树时将各个模式串结束位置打上对应标记
在匹配时累加标记，做完后统计一遍即可。
注意卡空间！！！

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f|=(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
string s[155],t;
int trie[1000005][27],cnt,word[1000005];
int fail[1000005],ans[1000005];
inline void add(int l)
{
    int root=0,len=s[l].size();
    for (register int i=0;i<len;++i)
        {
        int x=s[l][i]-'a'+1;
        if (!trie[root][x])
           trie[root][x]=++cnt;
        root=trie[root][x];
        }
    word[root]=l;
}
inline void get_fail()
{
    queue <int> q;
    for (register int i=1;i<=26;++i)
        if (trie[0][i])
           fail[trie[0][i]]=0,q.push(trie[0][i]);
    while (!q.empty())
          {
          int x=q.front();
          q.pop();
          for (register int i=1;i<=26;++i)
              {
              if (trie[x][i])
                 fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
              else
                 trie[x][i]=trie[fail[x]][i];
              }
          }
}
inline void query()
{
    int len=t.size(),now=0;
    for (register int i=0;i<len;++i)
        {
        now=trie[now][t[i]-'a'+1];
        for (register int j=now;j;j=fail[j])
            ans[word[j]]++;
        }
}
inline void get_ans()
{
    int maxx=0;
    for (register int i=1;i<=n;++i)
        maxx=max(maxx,ans[i]);
    printf("%d\n",maxx);
    for (register int i=1;i<=n;++i)
        if (ans[i]==maxx)
           cout<<s[i]<<endl;
}
inline void clear()
{
    memset(fail,0,sizeof(fail));
    memset(word,0,sizeof(word));
    memset(ans,0,sizeof(ans));
    memset(trie,0,sizeof(trie));
}
int main(){
    while (n=read())
          {
          clear();
          for (register int i=1;i<=n;++i)
              cin>>s[i],add(i);
          get_fail();
          cin>>t;
          query(),get_ans();
          }
    return 0;
}

$2^o$ P5357 【模板】AC自动机（二次加强版）

题解：

此题向我们反映出一个问题：

其实我们说的匹配方式：顺着fail跳是可以被卡的。
如果出题人弄一个fail长为n的数据，我们的匹配操作将会被卡掉。
类似于匹配串：aaaaaaaaaa……的情况即可HACK。

那么如何优化呢？

我们仔细思考

发现在学习 $AC$ 自动机时，大部分用的是 $KMP$ 的套路，并没有将 $AC$ 自动机是一个自动机的优势发挥！

我们其实可以发现

我们构造出来的自动机其实与Trie树没有关系！
AC自动机只与通过fail指针连的边有关。

于是我们可以不看原 $Trie$ 树边，只看 $fail$ 边，会发现他也构成了一颗树！我们将其称为 $fail$ 树

再联想 $fail$ 的定义(也就是 $next$ 的定义)中有这样一条：

前缀与后缀相等！
所以说fail树同时与前缀，后缀有关系。

由字符串的性质我们可以知道：

前缀的后缀就是子串

由于这一性质，我们可以发现：

以某一模式串结尾字母为根的子树，其节点访问次数之和
就是原模式串匹配次数。

所以：
我们只需要

1.预处理出fail数组
2.建立fail树，将文本串的每个字符累加到fail树节点的访问次数中
3.求出以模式串结尾字母为根的子树访问次数之和。
即可保证匹配时间在O(n)内，又同KMP复杂度分析，求fail数组复杂度O(m),所以总共O(n+m).

通过AC自动机的fail树性质，我们成功优化了AC自动机算法，使其拥有了稳定的线性复杂度！

AC代码：

//The code is from dxbdly
#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int x=0;
    char c=getchar();
    bool f=0;
    while (!isdigit(c))
          f=f|(c=='-'),c=getchar();
    while (isdigit(c))
          x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return f?-x:x;
}
int n;
string s;
struct node{
    int v,nex;
}edge[200005];
int head[200005],len,siz[200005];
int trie[200005][27],cnt,word[200005],fail[200005];
inline void make_map(int u,int v)
{
    len++;
    edge[len].nex=head[u];
    edge[len].v=v;
    head[u]=len;
}
inline void add(int l)
{
    int root=0,len=s.size();
    for (register int i=0;i<len;++i)
        {
        int x=s[i]-'a'+1;
        if (!trie[root][x])
           trie[root][x]=++cnt;
        root=trie[root][x];
        }
    word[l]=root;
}
inline void get_fail()
{
    queue <int> q;
    for (register int i=1;i<=26;++i)
        if (trie[0][i])
           fail[trie[0][i]]=0,q.push(trie[0][i]);
    while (!q.empty())
          {
          int x=q.front();
          q.pop();
          for (register int i=1;i<=26;++i)
              {
              if (trie[x][i])
                 fail[trie[x][i]]=trie[fail[x]][i],q.push(trie[x][i]);
              else
                 trie[x][i]=trie[fail[x]][i];
              }
          }
}
inline void make()
{
    int len=s.size(),now=0;
    for (register int i=0;i<len;++i)
        {
        now=trie[now][s[i]-'a'+1];
        ++siz[now];
        }
    for (register int i=1;i<=cnt;++i)
        make_map(fail[i],i);
}
inline void search(int x,int fa)
{
    for (register int i=head[x];i;i=edge[i].nex)
        {
        int y=edge[i].v;
        if (y==fa)
           continue;
        search(y,x);
        siz[x]+=siz[y];
        }
}
int main(){
    n=read();
    for (register int i=1;i<=n;++i)
        cin>>s,add(i);
    get_fail();
    cin>>s;
    make(),search(0,-1);
    for (register int i=1;i<=n;++i)
        printf("%d\n",siz[word[i]]);
    return 0;
}

内容目录

添加新批注

在作者公开此批注前，只有你和作者可见。

私有
公开
删除

回复批注