自动搬运

查看原文

来自洛谷，原作者为

	AuZeb 电棍下乡

搬运于2025-08-24 22:01:49，当前版本为作者最后更新于2025-03-13 20:50:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识

失配树和最近公共祖先。

思路与做法

将原问题转换为在失配树上寻找最近公共祖先，主要是因为以下两个原因：

• 失配树的性质：在失配树中，从根节点到任意节点的路径所代表的字符串，必然是字典树中从根节点到该节点路径所代表字符串的后缀。例如，若字典树中有节点对应字符串 abc，在失配树中，从根节点到该节点路径上的节点对应的字符串 c、bc、abc 都是 abc 的后缀。
• 题目要求找出两个地区描述到指定位置的串的最长公共后缀。假设两个地区描述分别为 $s_1$ 和$s_2$，在字典树中找到这两个描述对应位置的节点 $n_1$ 和 $n_2$。因为失配树的性质，从根节点到 $n_1$ 和 $n_2$ 路径上的节点对应的字符串分别是 $s_1$ 和 $s_2$ 的后缀。那么，$n_1$ 和 $n_2$ 在失配树中的最近公共祖先节点 $lca$，从根节点到 $lca$ 的路径所代表的字符串，就是 $s_1$ 和 $s_2$ 的最长公共后缀。这是因为最近公共祖先的路径是同时能到达 $n_1$ 和 $n_2$ 的最长公共路径，也就对应着两个地区描述的最长公共后缀。

理解了上面的，就比较简单了，给所有编码的每个前缀构建字典树，然后跑一遍构建失配树，最后直接输出根到该最近公共祖先的值（注意是原图上的值），样例如下图：

代码

由于遭受了 MLE 的重创，迫不得已将部分 vector 换成了数组，可能使可读性下降。vector 邻接表与链式前向星有内存性能上的差异，因为 vector 扩充时是默认多申请 $2$ 倍空间，所以像这道变态的题目可能会卡内存只能用链式前向星的写法写。

#include<bits/stdc++.h>
#define maxn 1000006
#define mod 1000000007
using namespace std;
int ch[maxn][26],idx=0,fail[maxn];
long long va[maxn];
int Id[maxn*2],len=0,Idx=0,Len[maxn];
// 注意输入的字符串总长度可能超过 tot！
struct Tree{int ne,to;}tr[maxn*2]; // 失配树。
// 原先 Id[i][j] 表示第 i 个表示的第 j 个地区对应的字典树的值，由于 vector 炸了，就用 Id[i]+Len[i] 代替了。
int k=0,head[maxn];
void add(int u,int v){k++,tr[k].to=v,tr[k].ne=head[u],head[u]=k;}
void ins(int id,string s){
	int u=0;
	for(int i=0;i<s.length();i++){
		if(!ch[u][s[i]-'a']) ch[u][s[i]-'a']=++idx;
		va[ch[u][s[i]-'a']]=(va[u]*26+(s[i]-'a'))%mod, // 计算根到该节点的值。
		u=ch[u][s[i]-'a'],Id[++Idx]=u; // 存储每个地区对应字典树上的编号。
	}
}
void bul(){ // 建立失配数组和失配树。
	queue<int> q;
	for(int i=0;i<26;i++) if(ch[0][i])
		q.push(ch[0][i]),add(0,ch[0][i]),add(ch[0][i],0);
	while(!q.empty()){
		int u=q.front(); q.pop();
		for(int i=0;i<26;i++)
			if(ch[u][i])
				fail[ch[u][i]]=ch[fail[u]][i],q.push(ch[u][i]),
				add(ch[u][i],fail[ch[u][i]]),
				add(fail[ch[u][i]],ch[u][i]);
			else ch[u][i]=ch[fail[u]][i];
	}
}
int dfn[maxn],tim=0,st[20][maxn]; // dfs 序 +ST 表找最近公共祖先。
// 详见 https://www.luogu.com.cn/article/pu52m9ue。
int get(int x,int y){
	return dfn[x]<dfn[y]?x:y;
}
struct Node{int x,f;};
void dfs(int u,int fa){ // 用迭代替代了递归。
	stack<Node> stk;
	stk.push({0,0});
	while (!stk.empty()){
		int u=stk.top().x,fa=stk.top().f; stk.pop();
		if(dfn[u]==0){
			tim++,dfn[u]=tim,st[0][tim]=fa;
			for(int i=head[u];i;i=tr[i].ne)
				if(tr[i].to!=fa) stk.push({tr[i].to, u});
		}
	}
}
int lca(int u,int v){
	if(u==v) return u;
	u=dfn[u],v=dfn[v]; if(u>v) swap(u,v);
	int dis=__lg(v-u); u++;
	return get(st[dis][u],st[dis][v-(1<<dis)+1]);
}
int main(){
	int n; cin>>n; string s;
	for(int i=1;i<=n;i++) cin>>s,ins(i,s),len+=s.length(),Len[i]=len;
	// Len[i] 表示前 i 行的总地区数。
	bul(),dfs(0,0);
	for(int i=1;i<=__lg(idx+1);i++)
		for(int j=1;j+(1<<i)-1<=idx+1;j++)
			st[i][j]=get(st[i-1][j],st[i-1][j+(1<<i-1)]);
	int m,i,j,k,l,u,v; cin>>m; while(m--)
		cin>>i>>j>>k>>l,u=Id[Len[i-1]+j],v=Id[Len[k-1]+l],cout<<va[lca(u,v)]<<"\n";
	return 0;
}