CodeForces - 547E Mike and Friends
\(\mathbb{D}\rm escription\)
\(\rm Link.\)
\(\mathbb{S}\rm olution\)
还有一个广义 \(\rm sam\) 的做法，但是我还不会广义 \(\rm sam\)，所以等学会了再回来填坑 ˉ_(ツ)_/ˉ。
\(\text{Method 1}\)：\(\rm ac\) 自动机
\(\rm ac\) 自动机的经典题目。先将所有字符串插入自动机，再将询问差分，把字符串按编号从小到大插入 \(\rm fail\) 树：其实就是将字符串每个前缀的结尾在 \(\rm fail\) 树上的节点加一，这样查询时直接查询对应字符串的子树和，这个字符串也就对应着之前某个前缀的后缀。复杂度带个 \(\log\).
\(\text{Method 2}\)：根号
讲题人又说是经典操作，我又不会 /kk.
一个重要的结论就是：当一堆字符串总长度为 \(N\) 时，字符串长度的种类不超过 \(\sqrt N\) 种。证明也很简单，就是 \(1\) 到 \(\sqrt N\) 的等差数列。
这有啥用呢？我们还是将询问差分，同时也对询问按 \(|s_k|\) 分类。然后枚举字符串长度 \(l\)，做一个扫描线，将当前扫描到的字符串所有长度为 \(l\) 的子串的哈希值插进哈希表里，同时统计相同哈希值的个数。那么询问就直接查询对应哈希值的个数即可。时间复杂度 \(\mathcal O(n\sqrt n)\)，胜在代码及其好写。
$\mathbb{C}\rm ode $
\(\text{Method 1}\)：\(\rm ac\) 自动机
# include
# include
# define print(x,y) write(x), putchar(y)
template
inline T read(const T sample) {
T x=0; char s; bool f=0;
while(!isdigit(s=getchar())) f|=(s=='-');
for(; isdigit(s); s=getchar()) x=(x<<1)+(x<<3)+(s^48);
return f? -x: x;
}
template
inline void write(T x) {
static int writ[50], w_tp=0;
if(x<0) putchar('-'), x=-x;
do writ[++w_tp] = x-x/10*10, x/=10; while(x);
while(putchar(writ[w_tp--]^48), w_tp);
}
# include
# include
# include
using namespace std;
typedef pair par;
const int maxn = 2e5+5;
const int maxq = 5e5+5;
char s[maxn];
vector e[maxn];
vector Q[maxn];
int p[maxn],dfn[maxn],Dfn,f[maxn];
int n,q,idx,ans[maxq],c[maxn],sz[maxn];
struct node {
int fa,to[26];
} t[maxn];
inline int ins() {
int len = strlen(s+1), p=0;
for(int i=1;i<=len;++i) {
int d = s[i]-'a';
if(!t[p].to[d]) f[t[p].to[d]=++idx]=p;
p = t[p].to[d];
}
return p;
}
inline void buildEdges() {
for(int i=1;i<=idx;++i)
e[t[i].fa].emplace_back(i);
}
void dfs(int u) {
dfn[u] = ++Dfn; sz[u]=1;
for(const auto& v:e[u]) dfs(v), sz[u]+=sz[v];
}
inline void getFail() {
queue q;
for(int i=0;i<26;++i)
if(t[0].to[i]) q.push(t[0].to[i]);
while(!q.empty()) {
int u=q.front(); q.pop();
for(int i=0;i<26;++i)
if(!t[u].to[i]) t[u].to[i]=t[t[u].fa].to[i];
else t[t[u].to[i]].fa=t[t[u].fa].to[i], q.push(t[u].to[i]);
}
}
inline int lowbit(int x) { return x&-x; }
inline void add(int x) {
while(x<=idx) ++c[x], x+=lowbit(x);
}
inline int ask(int l,int r,int ret=0) {
for(--l; l; l-=lowbit(l)) ret-=c[l];
for(; r; r-=lowbit(r)) ret+=c[r];
return ret;
}
int main() {
n=read(9), q=read(9);
for(int i=1;i<=n;++i)
scanf("%s",s+1), p[i]=ins();
for(int i=1;i<=q;++i) {
int l=read(9), r=read(9), k=read(9);
Q[l-1].emplace_back(make_pair(-i,k));
Q[r].emplace_back(make_pair(i,k));
}
getFail(), Dfn=-1, buildEdges(), dfs(0);
for(int i=1;i<=n;++i) {
int x=p[i];
while(x) add(dfn[x]), x=f[x];
for(const auto& t:Q[i]) {
x=p[t.second]; int tmp = ask(dfn[x],dfn[x]+sz[x]-1);
if(t.first>0) ans[t.first]+=tmp; else ans[-t.first]-=tmp;
}
}
for(int i=1;i<=q;++i) print(ans[i],'\n');
return 0;
}
\(\text{Method 2}\)：根号
Believe in yourself.