题意：
给定 \(n\) 个不同的字符串 \(s_1,\cdots,s_n\)。\(m\) 次询问，每次给出字符串 \(t\)，对所有在 \(t\) 中出现的 \(s_i\) 求出其出现次数，并用题目指定的 Hash 方式得到一个结果并返回。
\(\sum |s_i|,\sum |t_j|\leq L=10^6\)。
题解：
即我们得找出每个在 \(t\) 中出现的 \(s_i\) 并单独地统计它们的出现次数。
我们先估计有多少个 \(s_i\) 在 \(t\) 中出现了。一个初步的估计是：注意到 \(s_1,\cdots,s_n\) 共有 \(\sqrt L\) 种不同的长度，那么以 \(t\) 中某固定位置结尾的 \(s_i\) 有至多 \(\sqrt L\) 个，那么所有 \(s_i\) 在 \(t\) 中的出现次数至多为 \(|t|\sqrt L\)。
根据上述推导我们可以得到一个做法：建出 \(s_i\) 的 AC 自动机，我们只需对每个节点记录其 fail 树的祖先中最近的出现的 \(s_i\)，然后每次用 \(t\) 在 AC 自动机上走并对经过的每个节点暴力向上跳出现过的 \(s_i\) 并贡献即可。时间复杂度 \(O(L\sqrt L)\)。
一个更精细的界是：考虑长度 \(\leq B\) 的所有 \(s_i\)，根据类似地推导我们可以知道它们至多有 \(B|t|\) 个出现过；而对于长度 \(>B\) 的所有 \(s_i\)，首先它们只有 \(L/B\) 个，其次，它们会在某个 \(t_j\) 中出现当且仅当 \(|t_j|\geq B\)，所以只有 \(L/B\) 个可能的 \(t_j\)，于是所有 \(t_j\) 的出现过的这种 \(s_i\) 的数量的和不超过 \((L/B)^2\)。取 \(B=L^{1/3}\) 发现所有 \(t_j\) 的出现过的 \(s_i\) 的数量和不超过 \(L^{4/3}\)。
第一个分析给出的是所有 \(s_i\) 在 \(t\) 中出现次数的和的界，而第二个分析给出的是在 \(t\) 中出现过的 \(s_i\) 的数量的界。
那我们考虑对于 \(t\) 在 AC 自动机上经过的点先暴力往上跳，如果之前跳过了我们就不必跳了。据此建出一棵以 \(t\) 的每个前缀、以及所有在 \(t\) 中出现的 \(s_i\) 为关键点的虚树（注意不是严格的虚树，比如一些 lca 我们没建出来，但它们是不重要的），然后在这棵树上 DP 即可。
时间复杂度 \(O(L^{3/4})\)。
通过如下构造可以证明第二个界是紧的：构造 \(t\)，其每个字符都不同，且 \(|t|=L^{1/3}\)。把 \(t\) 的所有子串当成 \(s_1,\cdots,s_n\)，那么 \(n=O(L^{2/3})\)，\(\sum s_i=O(L)\)。那么每个 \(s_i\) 都在 \(t\) 中出现过，从而如果我们每次都询问 \(t\) 的话，总共的出现过的 \(s_i\) 的数量为 \(O(L^{4/3})\)。
由此可以看出如何猜出 \(O(L^{4/3})\) 的上界：假设我们要卡这个次数，显然是每次都问相同的串 \(t\)，而显然所有 \(s_i\) 都在 \(t\) 中出现时最优的，而显然我们会将 \(s_i\) 设置为 \(t\) 的小于等于某个 \(K\) 的所有子串，共 \(K|t|\) 个，长度总和为 \(K^2|t|\)。那么问题转为，在 \(K^2|t|\leq L\) 且 \(K\leq |t|\) 的前提下，如何使得 \(K|t|\cdot \frac{L}{|t|}\) 最大。那么显然是取 \(K=|t|=L^{1/3}\)。然后再想如何严格地证明。
#include<bits/stdc++.h>
#define N 200010
#define L 2000010
using namespace std;
namespace poww
{
const int B=200000;
unsigned pw[B],pwB[B+1];
void init()
{
pw[0]=pwB[0]=1;
for(int i=1;i<B;i++) pw[i]=pw[i-1]*3;
pwB[1]=pw[B-1]*3;
for(int i=2;i<B;i++) pwB[i]=pwB[i-1]*pwB[1];
}
unsigned query(long long x){return pwB[x/B]*pw[x%B];}
}
int node,ch[L][26],fail[L],id[L],jump[L];
void insert(int _id)
{
static char s[N];
scanf("%s",s+1);
int n=strlen(s+1),u=0;
for(int i=1;i<=n;i++)
{
int v=s[i]-'a';
if(!ch[u][v]) ch[u][v]=++node;
u=ch[u][v];
}
id[u]=_id;
}
void build()
{
queue<int> q;
for(int i=0;i<26;i++)
if(ch[0][i]) q.push(ch[0][i]);
while(!q.empty())
{
int u=q.front();
q.pop();
if(id[fail[u]]) jump[u]=fail[u];
else jump[u]=jump[fail[u]];
for(int i=0;i<26;i++)
{
if(ch[u][i])
{
fail[ch[u][i]]=ch[fail[u]][i];
q.push(ch[u][i]);
}
else ch[u][i]=ch[fail[u]][i];
}
}
}
void query(int _n)
{
static char t[N];
static int du[L],cnt[L];
scanf("%s",t+1);
int n=strlen(t+1);
for(int u=0,i=1;i<=n;i++)
{
u=ch[u][t[i]-'a'],cnt[u]++;
for(int x=u;x&&(++du[x])<=1;x=jump[x]);
}
queue<int> q;
for(int u=0,i=1;i<=n;i++)
{
u=ch[u][t[i]-'a'];
if(!(--du[u])) q.push(u);
}
unsigned ans=_n;
while(!q.empty())
{
int u=q.front();
q.pop();
if(id[u]) ans+=poww::query(1ll*id[u]*cnt[u])-1;
int f=jump[u];
cnt[f]+=cnt[u],cnt[u]=0;
if(!(--du[f])) q.push(f);
}
printf("%u\n",ans);
}
int main()
{
poww::init();
int T,n,m;
scanf("%d%d%d",&T,&n,&m);
for(int i=1;i<=n;i++) insert(i);
build();
for(int i=1;i<=m;i++) query(n);
return 0;
}
原文地址：http://www.cnblogs.com/ez-lcw/p/16908550.html
