Description
yz是Z国的领导人，他规定每个地区的名字只能为26个小写拉丁字母的一个。由于地 区数有可能超过26个，便产生了一个问题，如何辨别名字相同的地区？于是yz规定，一个 地区的描述必须包含它的所有上级，且上级按次序排列。于是，一个地区的描述是一个字符 串。比如说，一个地区的名字为c，它的上级为b，b的上级为a，a没有上级，那么这个地 区就描述为abc。显然，这个描述同时包含了c的上级b和b的上级a的描述，分别为ab和a。 值得注意的是，每个地区最多有一个上级，同一上级的地区之间名字不同，没有上级的 地区之间名字不同。现在，yz对外公布了n个地区的描述，这些描述中包含了Z国所有地区的描述，并让 你处理来访者的旅行问题。现有m对人访问这个国家，对于每对人，第一个人喜欢第i个描述中的第j个地区，设 这个地区描述为s1，第二个人喜欢第k个描述中的第l个地区，设这个地区描述为s2。他们为了统一行程，决定访问描述为s的地区（显然他们只关心地区的名字，并非是地区本身）， 设s的长度为t，s需要满足以下条件：
1：t<=j, t<=l;
1：s[1..t] = s1[j-t+1 … j], s[1..t] = s2[l-t+1 … l]；（即s为s1中1到k位 与s2中1到l位的公共后缀）
2：t最大化。
为了不使输出过大，你只需把这个字符串按照如下生成的26进制数转成10进制后mod 1000000007后输出。
就是求一个最长公共后缀，并且还是一个前缀。考虑一下，后缀相同？？？fail指针的交点？？？还要最长是个前缀？？？这不lca吗？？？所以就是求fail树上的lca。然后在build的时候就将串的10进制递推出来。就好了。
空间很值得注意啊。MLE*2.队列的空间炸了。另外lca初始化的时候没必要用bfs序。数组的就好多了直接循环下标。
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,x1,x2,y1,y2,m;
char st[1001000];
const ll mod=1000000007;
struct trie
{
trie *ch[26],*fa[22];
int deep;
int ans;
trie()
{
memset(ch,0,sizeof(ch));
memset(fa,0,sizeof(fa));
deep=0; ans=0;
}
}*root=new trie();
vector<trie*>map[1001000];
void insert(int x)
{
int len=strlen(st+1);
trie *p=root;
for(int i=1;i<=len;i++)
{
if(!p->ch[st[i]-'a'])
p->ch[st[i]-'a']=new trie(),p->ch[st[i]-'a']->ans=(1ll*p->ans*26%mod+st[i]-'a')%mod;
p=p->ch[st[i]-'a'];
map[x].push_back(p);
}
}
void build_ac_auto()
{
static trie* q[1000010];
int l=1,r=0;
for(int i=0;i<26;i++)
if(root->ch[i])
root->ch[i]->fa[0]=root,
root->ch[i]->deep=1,
q[++r]=root->ch[i];
while(l<=r)
{
trie *p=q[l]; l++;
for(int i=0;i<26;i++)
if(p->ch[i])
{
trie* tmp=p->fa[0];
while(tmp!=root&&!tmp->ch[i]) tmp=tmp->fa[0];
if(tmp->ch[i]) tmp=tmp->ch[i];
p->ch[i]->fa[0]=tmp;
p->ch[i]->deep=tmp->deep+1;
q[++r]=p->ch[i];
}
}
for(int i=1;i<=20;i++)
for(int j=1;j<=r;j++)
q[j]->fa[i]=q[j]->fa[i-1]->fa[i-1];
}
trie* lca(trie* x,trie* y)
{
if(x->deep<y->deep) swap(x,y);
for(int i=20;i>=0;i--)
if(x->fa[i]->deep>=y->deep) x=x->fa[i];
if(x==y) return x;
for(int i=20;i>=0;i--)
if(x->fa[i]!=y->fa[i]) x=x->fa[i],y=y->fa[i];
return x->fa[0];
}
int main()
{
for(int i=0;i<=20;i++) root->fa[i]=root;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%s",st+1);
insert(i);
}
build_ac_auto();
scanf("%d",&m);
while(m--)
{
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
printf("%d\n",lca(map[x1][y1-1],map[x2][y2-1])->ans);
}
return 0;
}