欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

石油大--Contest2022 - 2020年秋季组队训练赛第二场--17100 Problem D、Find String in a Grid （AC自动机）

程序员文章站 2022-06-08 08:25:40
...

题面：
石油大--Contest2022 - 2020年秋季组队训练赛第二场--17100 Problem D、Find String in a Grid （AC自动机）
题意：
给定一个 R∗CR*C 的字符矩阵，由大写字母构成。
有 qq 个询问，每次给定一个由大写字母构成的字符串，问这个字符串在这个字符矩阵中出现了多少次。
某个字符串在矩阵中出现定义为：这个字符串在矩阵中的存在形式是先往右匹配再往下匹配。其中往右往下的长度均可以为0。

题解：
考虑离线 qq 个查询，将这 qq 个查询建立 AC自动机。

然后将 R∗CR*C 的字符矩阵中的每个往右往下的串（枚举第 ii 行，枚举拐点 jj）在 AC自动机上匹配，最后在 failfail 树上求一遍 dfsdfs 即可。（其实获得拓扑序之后就没有必要再建立一次 failfail 树了，但是为了好理解，我还是把它建立出来了）。

设字符矩阵为 s[i][j]s[i][j]
但是这样做会进行重复匹配。譬如第 ii 行和第 i+1i+1 行都是枚举的拐点 jj，那么 s[i+1][j],s[i+2][j],...,s[R][j]s[i+1][j],s[i+2][j],...,s[R][j] 这一些后缀就会重复计算。

一种可行的处理办法是，我们在进行第 ii 行拐点 jj 在AC自动上面的匹配的时候，我们对串 s[i][1]−s[i][j]−s[R][j]s[i][1]-s[i][j]-s[R][j] 上面的节点都做 +1+1 处理，对 s[i][j]−s[R][j]s[i][j]-s[R][j] （注意这是一个新串，从根节点开始匹配的） 上面的节点都做 −1-1 处理，这点就相当于抵消了 s[i][1]−s[i][j]−s[R][j]s[i][1]-s[i][j]-s[R][j] 的后缀 s[i][j]−s[R][j]s[i][j]-s[R][j] 的贡献。

那么我们这样处理的话，每一列的贡献其实还都没有计算，这是我们只需要枚举每一列的串 s[1][j]−s[R][j]s[1][j]-s[R][j] 在AC自动机上匹配即可。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
namespace onlyzhao
{
    #define ui unsigned int
    #define ll long long
    #define llu unsigned ll
    #define ld long double
    #define pr make_pair
    #define pb push_back
    #define lc (cnt<<1)
    #define rc (cnt<<1|1)
    #define len(x)  (t[(x)].r-t[(x)].l+1)
    #define tmid ((l+r)>>1)
    #define fhead(x) for(int i=head[(x)];i;i=nt[i])
    #define max(x,y) ((x)>(y)?(x):(y))
    #define min(x,y) ((x)>(y)?(y):(x))
    #define one(n) for(int i=1;i<=(n);i++)
    #define rone(n) for(int i=(n);i>=1;i--)
    #define fone(i,x,n) for(int i=(x);i<=(n);i++)
    #define frone(i,n,x) for(int i=(n);i>=(x);i--)
    #define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))
    #define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))
    #define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
    #define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)
    #define fvc(vc) for(int i=0;i<vc.size();i++)
    #define frvc(vc) for(int i=vc.size()-1;i>=0;i--)
    #define forvc(i,vc) for(int i=0;i<vc.size();i++)
    #define forrvc(i,vc) for(int i=vc.size()-1;i>=0;i--)
    #define cls(a) memset(a,0,sizeof(a))
    #define cls1(a) memset(a,-1,sizeof(a))
    #define clsmax(a) memset(a,0x3f,sizeof(a))
    #define clsmin(a) memset(a,0x80,sizeof(a))
    #define cln(a,num) memset(a,0,sizeof(a[0])*num)
    #define cln1(a,num) memset(a,-1,sizeof(a[0])*num)
    #define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)
    #define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)
    #define sc(x) scanf("%d",&x)
    #define sc2(x,y) scanf("%d%d",&x,&y)
    #define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define scl(x) scanf("%lld",&x)
    #define scl2(x,y) scanf("%lld%lld",&x,&y)
    #define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
    #define scf(x) scanf("%lf",&x)
    #define scf2(x,y) scanf("%lf%lf",&x,&y)
    #define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)
    #define scs(x) scanf("%s",x+1)
    #define scs0(x) scanf("%s",x)
    #define scline(x) scanf("%[^\n]%*c",x+1)
    #define scline0(x) scanf("%[^\n]%*c",x)
    #define pcc(x) putchar(x)
    #define pc(x) printf("%d\n",x)
    #define pc2(x,y) printf("%d %d\n",x,y)
    #define pc3(x,y,z) printf("%d %d %d\n",x,y,z)
    #define pck(x) printf("%d ",x)
    #define pcl(x) printf("%lld\n",x)
    #define pcl2(x,y) printf("%lld %lld\n",x,y)
    #define pcl3(x,y,z) printf("%lld %lld %d\n",x,y,z)
    #define pclk(x) printf("%lld ",x)
    #define pcf2(x) printf("%.2f\n",x)
    #define pcf6(x) printf("%.6f\n",x)
    #define pcf8(x) printf("%.8f\n",x)
    #define pcs(x) printf("%s\n",x+1)
    #define pcs0(x) printf("%s\n",x)
    #define pcline(x) printf("%d**********\n",x)
    #define casett int tt;sc(tt);int pp=0;while(tt--)
 
    char buffer[100001],*S,*T;
    inline char Get_Char()
    {
        if (S==T)
        {
            T=(S=buffer)+fread(buffer,1,100001,stdin);
            if (S==T) return EOF;
        }
        return *S++;
    }
    inline int read()
    {
        char c;int re=0;
        for(c=Get_Char();c<'0'||c>'9';c=Get_Char());
        while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();
        return re;
    }
};
using namespace onlyzhao;
using namespace std;
 
const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=250100;
const int maxm=510;
const int up=100100;
 
char s[510][510],str[maxn];
 
int t[maxn][26];
int sum[maxn],fail[maxn],ed[maxn];
int q[maxn],cnt=0;
 
void _insert(int i)
{
    int p=0,len=strlen(str+1);
    int k;
    for(int i=1;i<=len;i++)
    {
        k=str[i]-'A';
        if(!t[p][k]) t[p][k]=++cnt;
        p=t[p][k];
    }
    ed[i]=p;
}
 
 
void getfail(void)
{
    int l=1,r=0;
    for(int i=0;i<26;i++)
    {
        if(t[0][i])
        {
            fail[t[0][i]]=0,q[++r]=t[0][i];
        }
    }
    while(l<=r)
    {
        int now=q[l++];
        {
            for(int i=0;i<26;i++)
            {
                int p=t[now][i];
                if(p)
                    fail[p]=t[fail[now]][i],q[++r]=p;
                else t[now][i]=t[fail[now]][i];
            }
        }
    }
}
 
void build(int q)
{
    for(int i=1;i<=q;i++)
    {
        scanf("%s",str+1);
        _insert(i);
    }
    getfail();
}
 
 
void get(int n,int m)
{
    for(int j=1;j<=m;j++)
    {
        int p=0;
        for(int i=1;i<=n;i++)
        {
            p=t[p][s[i][j]];
            sum[p]++;
        }
    }
 
    for(int i=1;i<=n;i++)
    {
        int p=0;
        for(int j=1;j<=m;j++)
        {
            int p1=p,p2=0;
            for(int k=i;k<=n;k++)
            {
                p1=t[p1][s[k][j]];
                p2=t[p2][s[k][j]];
                sum[p1]++;
                sum[p2]--;
            }
            p=t[p][s[i][j]];
        }
    }
}
 
 
int head[maxn],ver[maxn],nt[maxn],tot=1;
 
void add(int x,int y)
{
    ver[++tot]=y,nt[tot]=head[x],head[x]=tot;
}
 
void buildtree(void)
{
    for(int i=1;i<=cnt;i++)
        add(fail[i],i);
}
 
void dfs(int x)
{
    for(int i=head[x];i;i=nt[i])
    {
        int y=ver[i];
        dfs(y);
        sum[x]+=sum[y];
    }
}
 
void ans(int q)
{
    for(int i=1;i<=q;i++)
        printf("%d\n",sum[ed[i]]);
}
 
int main(void)
{
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++)
        scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
            s[i][j]-='A';
    }
    build(q);
    get(n,m);
    buildtree();
    dfs(0);
    ans(q);
    return 0;
}
相关标签： AC自动机

上一篇： CakePHP: HTTPS HTTP页面跳转导致登录信息丢失

下一篇： JQuery触发radio或checkbox的change事件详解

推荐阅读