C++14(g++5.4) 解法, 执行用时: 1083ms, 内存消耗: 245612K, 提交时间: 2020-08-07 10:17:23

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<vector>

using namespace std;

 

const int maxn = 1E6 + 10;

typedef long long LL;

const LL mo = 1000000007LL;

 

int n,m,cnt = 0,ch[maxn][26],f[maxn][20],L[maxn];

LL ans[maxn];

char c[maxn];

 

vector <int> pos[maxn];

queue <int> q;

 

int LCA(int a,int b)

{

	if (L[a] < L[b]) swap(a,b);

	int log;

	for (log = 0; L[a] - (1<<log) >= 0; log++); log--;

	for (int j = log; j >= 0; j--)

		if (L[a] - (1<<j) >= L[b])

			a = f[a][j];

	if (a == b) return ans[a];

	

	for (int j = log; j >= 0; j--)

		if (f[a][j] != f[b][j]) {

			a = f[a][j]; b = f[b][j];

		}

	return ans[f[a][0]];

}

 

int main()

{

	#ifdef YZY	

		freopen("yzy.txt","r",stdin);

	#endif

	

	cin >> n;

	for (int i = 1; i <= n; i++) {

		scanf("%s",c);

		int len = strlen(c);

		int x = 0;

		for (int j = 0; j < len; j++) {

			int po = c[j] - 'a';

			if (!ch[x][po]) {

				ch[x][po] = ++cnt;

				LL ADD = c[j] - 'a';

				ans[cnt] = (ans[x]*26LL + ADD)%mo;

			}

			x = ch[x][po];

			pos[i].push_back(x);

		}

	}

	

	for (int i = 0; i < 26; i++)

		if (ch[0][i]) {

			L[ch[0][i]] = 1;

			f[ch[0][i]][0] = 0;

			q.push(ch[0][i]);

		}

		

	while (!q.empty()) {

		int k = q.front(); q.pop();

		for (int i = 0; i < 26; i++) {

			int u = ch[k][i];

			if (!u) {

				ch[k][i] = ch[f[k][0]][i];

				continue;

			}

			int v = f[k][0];

			while (v && !ch[v][i]) v = f[v][0];

			L[u] = L[ch[v][i]] + 1;

			f[u][0] = ch[v][i];

			q.push(u);

		}

	}

	

	for (int j = 1; j < 20; j++)	

		for (int i = 1; i <= cnt; i++)

			f[i][j] = f[f[i][j-1]][j-1];

	

	cin >> m;

	while (m--) {

		int a,b,x,y;

		scanf("%d%d%d%d",&a,&b,&x,&y);

		printf("%d\n",LCA(pos[a][b-1],pos[x][y-1]));

	}

	return 0;

}

C++(clang++11) 解法, 执行用时: 1327ms, 内存消耗: 225944K, 提交时间: 2021-02-13 15:48:31

#include<cstdio>
const int mxn=1<<20;
const int mod=1e9+7;
int n,m;
int dep[mxn];
int dis[mxn];
int next[mxn][26],tot=1;
int st[mxn],ed[mxn<<1],tim;
inline void insert(char *s)
{
	int t=1;
	while(*s)
	{
		int c=*s++-'a';
		if(next[t][c]==0)
	    dis[next[t][c]=++tot]=(26LL*dis[t]+c)%mod;
	    t=next[t][c];
	    ed[++tim]=t;
	}
 } 
int fa[mxn][21];
inline void build()
{
	static int que[mxn],hd,tl;
	fa[1][0]=1;
	for(int i=0;i<26;++i)
	if(next[1][i])
	fa[que[tl++]=next[1][i]][0]=1;
	while(hd!=tl)
	{
		int t=que[hd++];
		if(t!=1)
		dep[t]=dep[fa[t][0]]+1;
		for(int i=1;i<=20;++i)
		fa[t][i]=fa[fa[t][i-1]][i-1];
		for(int i=0;i<26;++i)
		if(next[t][i])
		{
			int p=fa[t][0];
			while(p!=1&&!next[p][i])
			p=fa[p][0];
			if(next[p][i])
			fa[next[t][i]][0]=next[p][i];
			else
			fa[next[t][i]][0]=1;
			que[tl++]=next[t][i];
		}
	}
}
inline int lca(int a,int b)
{
	if(dep[a]<dep[b])
	a^=b^=a^=b;
	for(int i=20;~i;--i)
	if(dep[fa[a][i]]>=dep[b])
	a=fa[a][i];
	if(a==b)
	return a;
	for(int i=20;~i;--i)
	if(fa[a][i]!=fa[b][i])
	a=fa[a][i],b=fa[b][i];
	return fa[a][0];
}
signed main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{
		static char str[mxn];
		scanf("%s",str);
		st[i]=tim;
		insert(str);
	}
	build();
	scanf("%d",&m);
	for(int i=0;i<m;++i)
	{
		int s1,s2,l1,l2,p1,p2;
		scanf("%d%d%d%d",&s1,&l1,&s2,&l2);
		p1=ed[st[s1]+l1];
		p2=ed[st[s2]+l2];
		int t=lca(p1,p2);
		printf("%d\n",dis[t]);
	}
}