题意：
现有一个由大写字母构成的 \(n\) 行 \(m\) 列矩阵。
定义一个 \(L\) 型路径为，从矩阵某个位置开始，先向右走若干步，再向下走若干步，且不离开矩阵边界的路径。
定义一个 \(L\) 型字符串为对应的 \(L\) 型路径上字符依次连接起来组成的字符串。
现给定 \(q\) 次询问，每次给一个大写字母组成的字符串SS，询问矩阵中包含多少个等于SS的L型字符串。
\(n≤500,m≤500,q≤2×10^5\)，所有查询的字符串长度之和 \(≤2×10^5\)。
考虑将查询串存入 ACAM，处理出所有极长 \(L\) 型路径并做多模式串匹配，最后再在树上更新答案，可能需要简单的容斥，卡常。
#include<bits/stdc++.h>
#define N 800005
#define ll long long
#define pii pair<int,int>
#define pb push_back
#define fi first
#define se second
using namespace std;
struct ACAM{
int rt=1,cn=1,tr[N][26],le[N],fail[N],ed[N];
vector<int>g[N]; ll ans[N];
void addE(int x,int y){g[x].pb(y),g[y].pb(x);}
void ins(string s,int id){
int ln=(int)s.size(),u=rt;
for(int i=0;i<ln;i++){
int &v=tr[u][s[i]-'A'];
if(!v) v=(++cn);
le[v]=le[u]+1,u=v;
}ed[id]=u;
}void build(){
queue<int>q; q.push(1);
memset(fail,0,sizeof(fail));
for(int i=0;i<26;i++) tr[0][i]=1;
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=0;i<26;i++)
if(tr[u][i]) fail[tr[u][i]]=tr[fail[u]][i],q.push(tr[u][i]);
else tr[u][i]=tr[fail[u]][i];
if(u>1) g[fail[u]].pb(u);
}return;
}void dfs(int x){for(int &u:g[x]) dfs(u),ans[x]+=ans[u];}
}T; int n,m,Q,cn[26]; string s[505],q[N];
void add(string t,int d){
int u=T.rt;
for(int r=0;r<(int)t.size();r++)
u=T.tr[u][t[r]-'A'],T.ans[u]+=d;
}signed main(){
cin>>n>>m>>Q;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++) for(int j=0;j<m;j++)
cn[s[i][j]-'A']++;
for(int i=0;i<Q;i++) cin>>q[i],T.ins(q[i],i);
T.build();
for(int i=0;i<n-1;i++)
for(int j=1;j<m;j++){
string s0,t0; s0.clear(),t0.clear(); int u=T.rt;
for(int p=j;~p;--p) s0+=s[i][p];
reverse(s0.begin(),s0.end()),add(s0,-1);
for(int p=i;p<n;p++) t0+=s[p][j];
add(t0,-1),t0.erase(t0.begin()),add(s0+t0,1);
}
for(int i=0;i<n;i++){
int u=T.rt;
for(int j=0;j<m;j++)
T.ans[u=T.tr[u][s[i][j]-'A']]++;
}for(int j=0;j<m;j++){
int u=T.rt;
for(int i=0;i<n;i++)
T.ans[u=T.tr[u][s[i][j]-'A']]++;
}T.dfs(T.rt);
for(int i=0;i<Q;i++){
if(q[i].size()==1) T.ans[T.ed[i]]=cn[q[i][0]-'A'];
cout<<T.ans[T.ed[i]]<<endl;
}return 0;
}
```