题面：
题意：
给定一个 R∗C 的字符矩阵，由大写字母构成。
有 q 个询问，每次给定一个由大写字母构成的字符串，问这个字符串在这个字符矩阵中出现了多少次。
某个字符串在矩阵中出现定义为：这个字符串在矩阵中的存在形式是先往右匹配再往下匹配。其中往右往下的长度均可以为0。
题解：
考虑离线 q 个查询，将这 q 个查询建立 AC自动机。
然后将 R∗C 的字符矩阵中的每个往右往下的串（枚举第 i 行，枚举拐点 j）在 AC自动机上匹配，最后在 fail 树上求一遍 dfs 即可。（其实获得拓扑序之后就没有必要再建立一次 fail 树了，但是为了好理解，我还是把它建立出来了）。
设字符矩阵为 s[i][j]
但是这样做会进行重复匹配。譬如第 i 行和第 i+1 行都是枚举的拐点 j，那么 s[i+1][j],s[i+2][j],...,s[R][j] 这一些后缀就会重复计算。
一种可行的处理办法是，我们在进行第 i 行拐点 j 在AC自动上面的匹配的时候，我们对串 s[i][1]−s[i][j]−s[R][j] 上面的节点都做 +1 处理，对 s[i][j]−s[R][j] （注意这是一个新串，从根节点开始匹配的） 上面的节点都做 −1 处理，这点就相当于抵消了 s[i][1]−s[i][j]−s[R][j] 的后缀 s[i][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;
}
京公网安备 11010502036488号