竞赛讨论区 > 用KMP构建自动机
头像
四糸智乃
编辑于 2018-08-16 17:03
+ 关注

用KMP构建自动机

AC才发现打的是道假题,不知道发生了啥…。
题意:给你n(n<=4)个模式字符串,然后给你一个长度为l的操作序列,一开始是空字符串,接下来按照操作序列进行操作,问你每个时刻至少再加几个字符,使得你操作的字符串的后缀中出现至少一个模式字符串。(即字符串的结尾出现模式串)
预备知识:基于有限自动机的KMP算法构造思想https://blog.csdn.net/unoboros/article/details/33106353
因为n<=4,所以想到先对每个字符串建一个KMP“自动机”。对于输入操作,依次操作4台自动机,同时开4个数组记录每个时刻每台自动机所在的匹配状态。碰到退格键就使用记录数组直接回退状态。
然后…然后我就TLE 80了,然后首A还没了,心态有点崩。
分析后发现是因为强制的回退操作导致KMP每次fail的时间复杂度从均摊O(1)变为了O(n)。
举例说明:
图片说明
比如模式串为aaaaaaaaaaaaaaaaa….
总之就是1e5个左右的a
然后输入这么一个操作序列aaaaaaaaaa…aaaaaaaaab-b-b-b-b-b-b-b-b-b-b…
这样的话好不容易跑到最后一个状态,突然来个b,就要花费n的时间回到状态1正常来讲你kmp匹配的时候跑到最后一个状态至少要匹配成功n次,所以能均摊O(1),结果现在你强制回退一步就到1e5+5这个状态了,所以每次都花费n…被卡成O(n^2)摊不平了,所以用一个AC自动机中很常见的优化,去掉fail边,为每个匹配状态都补上其26个后继状态(见lrj大白书)。这样就不用均摊O(1)而是变成了真O(1)。

好多AC自动机版子应该是自带这个优化的…所以…可以建四台AC自动机来跑,贴贴版子就过了…感觉比E还签到。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
char s[5][MAXN],c[MAXN];
int n,fail[5][MAXN],len[5],save[5][MAXN],now,nexts[4][MAXN][26];
void getfail(char t[],int fail[],int k)
{
    fail[0]=fail[1]=0;int l=strlen(t);
    for(int i=1;i<l;++i)
    {
        int j=fail[i];
        while(j&&t[i]!=t[j])j=fail[j];
        fail[i+1]=t[j]==t[i]?j+1:0;
    }
    for(int i=0;i<=l;++i)
    {
        for(int j=0;j<26;++j)
        {
            nexts[k][i][j]=nexts[k][fail[i]][j];
        }
        if(i!=l)
        {
            nexts[k][i][t[i]-'a']=i+1;
        }
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%s",s[i]);
        getfail(s[i],fail[i],i);
        len[i]=strlen(s[i]);
    }
    scanf("%s",c);
    int l=strlen(c);
    int j[5]={0};
    int temp=-1;
    for(int i=1;i<=n;++i)
    {
        if(temp==-1||temp>len[i])temp=len[i];
    }
    printf("%d\n",temp);
    for(int i=0;i<l;++i)
    {
        if(c[i]=='-')
        {
            if(now)--now;
            for(int k=1;k<=n;++k)
            {
                j[k]=save[k][now];
            }
        }
        else
        {
            ++now;
            for(int k=1;k<=n;++k)
            {
                j[k]=nexts[k][j[k]][c[i]-'a'];
            }
        }
        for(int k=1;k<=n;++k)
        {
            save[k][now]=j[k];
        }
        int ans=-1;
        for(int k=1;k<=n;++k)
        {
            if(ans==-1||ans>len[k]-j[k])
            {
                ans=len[k]-j[k];
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐