A CodeForces-547E Mike and Friends *2800
肯定要建广义 SAM。
在每个 \(cur\) 打一个标记，没有区间限制就在对应节点上查一下后缀树子树标记总数，有区间限制线段树合并维护标记。
点击查看代码
int n,q;
char s[maxn];
int mark[maxn];
struct SegmentTree{
#define mid ((l+r)>>1)
int ch[maxn*40][2],tot;
int siz[maxn*40];
void insert(int &pos,int l,int r,int p){
if(!pos) pos=++tot;
++siz[pos];
if(l==r) return;
if(p<=mid) insert(ch[pos][0],l,mid,p);
else insert(ch[pos][1],mid+1,r,p);
}
int merge(int x,int y,int l,int r){
if(!x||!y) return x+y;
int pos=++tot;
siz[pos]=siz[x]+siz[y];
if(l==r) return pos;
ch[pos][0]=merge(ch[x][0],ch[y][0],l,mid);
ch[pos][1]=merge(ch[x][1],ch[y][1],mid+1,r);
return pos;
}
int query(int pos,int l,int r,int pl,int pr){
if(pl<=l&&r<=pr) return siz[pos];
int res=0;
if(ch[pos][0]&&pl<=mid) res+=query(ch[pos][0],l,mid,pl,pr);
if(ch[pos][1]&&pr>mid) res+=query(ch[pos][1],mid+1,r,pl,pr);
return res;
}
#undef mid
}S;
struct SuffixAutomaton{
int ch[maxn<<1][26],tot;
int len[maxn<<1],link[maxn<<1];
int rt[maxn<<1];
SuffixAutomaton(){
tot=0;
len[0]=0,link[0]=-1;
}
inline int extend(int last,int c,vector<int> ID){
int cur=++tot;
len[cur]=len[last]+1;
for(int i:ID) S.insert(rt[cur],1,n,i);
int p=last;
while(p!=-1&&!ch[p][c]){
ch[p][c]=cur;
p=link[p];
}
if(p==-1) link[cur]=0;
else{
int q=ch[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else{
int clone=++tot;
len[clone]=len[p]+1,link[clone]=link[q];
for(int i=0;i<26;++i) ch[clone][i]=ch[q][i];
while(p!=-1&&ch[p][c]==q){
ch[p][c]=clone;
p=link[p];
}
link[cur]=link[q]=clone;
}
}
return cur;
}
vector<int> E[maxn<<1];
void dfs(int u){
for(int v:E[u]){
dfs(v);
rt[u]=S.merge(rt[u],rt[v],1,n);
}
}
void solve(){
for(int i=1;i<=tot;++i){
E[link[i]].push_back(i);
}
dfs(0);
while(q--){
int l=read(),r=read(),k=read();
printf("%d\n",S.query(rt[mark[k]],1,n,l,r));
}
}
}SAM;
struct Trie{
int tr[maxn][26],tot;
int fa[maxn],last[maxn],C[maxn];
vector<int> ID[maxn];
inline void insert(int id){
int len=strlen(s+1);
int u=0;
for(int i=1;i<=len;++i){
int c=s[i]-'a';
if(!tr[u][c]) tr[u][c]=++tot;
fa[tr[u][c]]=u,C[tr[u][c]]=c;
ID[tr[u][c]].push_back(id);
u=tr[u][c];
}
mark[id]=u;
}
inline void build(){
queue<int> q;
for(int i=0;i<26;++i){
if(tr[0][i]) q.push(tr[0][i]);
}
while(!q.empty()){
int u=q.front();
q.pop();
last[u]=SAM.extend(last[fa[u]],C[u],ID[u]);
for(int i=0;i<26;++i){
if(tr[u][i]) q.push(tr[u][i]);
}
}
for(int i=1;i<=n;++i) mark[i]=last[mark[i]];
}
}T;
int main(){
n=read(),q=read();
for(int i=1;i<=n;++i){
scanf("%s",s+1);
T.insert(i);
}
T.build();
SAM.solve();
return 0;
}
B CodeForces-504E Misha and LCP on Tree
哈希，维护根到当前节点路径的正反哈希，询问二分 \(\mathrm{lcp}\)，需要支持查询树上 \(k\) 级祖先，倍增常数比树剖大。
也有一个 \(\log\) 的做法，先暴跳重链确定两条路径失配的重链，再在上面二分，但是不好写，树剖两个 \(\log\) 可过。
点击查看代码
inline int q_pow(int A,int B,int P){
int res=1;
while(B){
if(B&1) res=1ll*res*A%P;
A=1ll*A*A%P;
B>>=1;
}
return res;
}
int n,q;
char s[maxn];
int pw1[maxn],pw2[maxn];
int inv_pw1[maxn],inv_pw2[maxn];
struct Graph{
struct edge{
int to,nxt;
}e[maxn<<1];
int head[maxn],cnt;
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
e[++cnt].to=u,e[cnt].nxt=head[v],head[v]=cnt;
}
int fa[maxn],dep[maxn],siz[maxn],son[maxn];
int top[maxn],dfn[maxn],dfncnt,id[maxn];
int preh1[maxn],preh2[maxn],sufh1[maxn],sufh2[maxn];
void dfs1(int u,int f,int d){
fa[u]=f,dep[u]=d,siz[u]=1;
preh1[u]=(preh1[f]+1ll*s[u]*pw1[dep[u]]%mod1)%mod1;
preh2[u]=(preh2[f]+1ll*s[u]*pw2[dep[u]]%mod2)%mod2;
sufh1[u]=(1ll*sufh1[f]*base1%mod1+s[u])%mod1;
sufh2[u]=(1ll*sufh2[f]*base2%mod2+s[u])%mod2;
int maxson=-1;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==f) continue;
dfs1(v,u,d+1);
siz[u]+=siz[v];
if(siz[v]>maxson) maxson=siz[v],son[u]=v;
}
}
void dfs2(int u,int t){
top[u]=t,dfn[u]=++dfncnt,id[dfncnt]=u;
if(!son[u]) return;
dfs2(son[u],t);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa[u]||v==son[u]) continue;
dfs2(v,v);
}
}
inline int get_LCA(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>dep[top[v]]) swap(u,v);
v=fa[top[v]];
}
if(dep[u]>dep[v]) swap(u,v);
return u;
}
inline int get_fa(int u,int d){
int x=u;
while(dep[top[x]]>dep[u]-d) x=fa[top[x]];
return id[dfn[x]-(dep[x]-(dep[u]-d))];
}
inline int get_hash1(int u,int v,int d,int lca,int dis){
if(u==lca){
int w=get_fa(v,dis-d);
return (sufh1[w]-1ll*sufh1[fa[u]]*pw1[dep[w]-dep[fa[u]]]%mod1+mod1)%mod1;
}
else if(v==lca){
int w=get_fa(u,d-1);
return 1ll*(preh1[u]-preh1[fa[w]]+mod1)%mod1*inv_pw1[dep[w]]%mod1;
}
else{
int res=0;
if(d<=dep[u]-dep[lca]+1){
int w=get_fa(u,d-1);
res=1ll*(preh1[u]-preh1[fa[w]]+mod1)%mod1*inv_pw1[dep[w]]%mod1;
}
else{
res=1ll*(preh1[u]-preh1[fa[lca]]+mod1)%mod1*inv_pw1[dep[lca]]%mod1;
d-=dep[u]-dep[lca]+1;
int w=get_fa(v,dep[v]-dep[lca]-d);
res=1ll*res*pw1[dep[w]-dep[lca]]%mod1;
res=(res+(sufh1[w]-1ll*sufh1[lca]*pw1[dep[w]-dep[lca]]%mod1+mod1)%mod1)%mod1;
}
return res;
}
}
inline int get_hash2(int u,int v,int d,int lca,int dis){
if(u==lca){
int w=get_fa(v,dis-d);
return (sufh2[w]-1ll*sufh2[fa[u]]*pw2[dep[w]-dep[fa[u]]]%mod2+mod2)%mod2;
}
else if(v==lca){
int w=get_fa(u,d-1);
return 1ll*(preh2[u]-preh2[fa[w]]+mod2)%mod2*inv_pw2[dep[w]]%mod2;
}
else{
int res=0;
if(d<=dep[u]-dep[lca]+1){
int w=get_fa(u,d-1);
res=1ll*(preh2[u]-preh2[fa[w]]+mod2)%mod2*inv_pw2[dep[w]]%mod2;
}
else{
res=1ll*(preh2[u]-preh2[fa[lca]]+mod2)%mod2*inv_pw2[dep[lca]]%mod2;
d-=dep[u]-dep[lca]+1;
int w=get_fa(v,dep[v]-dep[lca]-d);
res=1ll*res*pw2[dep[w]-dep[lca]]%mod2;
res=(res+(sufh2[w]-1ll*sufh2[lca]*pw2[dep[w]-dep[lca]]%mod2+mod2)%mod2)%mod2;
}
return res;
}
}
inline void solve(){
while(q--){
int a=read(),b=read(),c=read(),d=read();
int lca1=get_LCA(a,b),lca2=get_LCA(c,d);
int dis1=dep[a]+dep[b]-2*dep[lca1]+1,dis2=dep[c]+dep[d]-2*dep[lca2]+1;
int l=1,r=min(dis1,dis2),ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(get_hash1(a,b,mid,lca1,dis1)==get_hash1(c,d,mid,lca2,dis2)&&get_hash2(a,b,mid,lca1,dis1)==get_hash2(c,d,mid,lca2,dis2)) ans=mid,l=mid+1;
else r=mid-1;
}
printf("%d\n",ans);
}
}
}G;
int main(){
n=read();
pw1[0]=1,pw2[0]=1;
for(int i=1;i<=n;++i) pw1[i]=1ll*pw1[i-1]*base1%mod1,pw2[i]=1ll*pw2[i-1]*base2%mod2;
inv_pw1[n]=q_pow(pw1[n],mod1-2,mod1),inv_pw2[n]=q_pow(pw2[n],mod2-2,mod2);
for(int i=n-1;i>=0;--i) inv_pw1[i]=1ll*inv_pw1[i+1]*base1%mod1,inv_pw2[i]=1ll*inv_pw2[i+1]*base2%mod2;
scanf("%s",s+1);
for(int i=1;i<n;++i){
int u=read(),v=read();
G.add_edge(u,v);
}
G.dfs1(1,0,0);
G.dfs2(1,1);
q=read();
G.solve();
return 0;
}