思路：
建立ac自动机，然后把fail树抽出来；
然后在fail树上走lca（神奇）；
代码：
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 1000005
#define mod 1000000007LL struct TreeNodeType {
int id; long long dis; TreeNodeType *next[],*fail; TreeNodeType()
{
id=,dis=,fail=NULL;
for(int i=;i<;i++) next[i]=NULL;
}
};
struct TreeNodeType *map[maxn<<],*que[maxn<<],*root; int n,m,deep[maxn<<],f[maxn<<],top[maxn<<],head[maxn<<];
int E[maxn<<],V[maxn<<],tot,cnt,len,size[maxn<<]; char ch[maxn<<]; vector<int>vec[maxn<<]; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} void dfs1(int now,int fa)
{
f[now]=fa,deep[now]=deep[fa]+,size[now]=;
for(int i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
dfs1(V[i],now),size[now]+=size[V[i]];
}
} void dfs2(int now,int chain)
{
top[now]=chain;int pos=;
for(int i=head[now];i;i=E[i])
{
if(V[i]==f[now]) continue;
if(size[V[i]]>size[pos]) pos=V[i];
}
if(pos) dfs2(pos,chain);else return ;
for(int i=head[now];i;i=E[i])
{
if(V[i]==pos||V[i]==f[now]) continue;
dfs2(V[i],V[i]);
}
} inline int lca(int x,int y)
{
for(;top[x]!=top[y];)
{
if(deep[top[x]]<deep[top[y]]) swap(x,y);
x=f[top[x]];
}
if(deep[x]>deep[y]) swap(x,y);
return x;
} int main()
{
in(n);root=new TreeNodeType;
root->id=++tot,map[root->id]=root;
for(int i=;i<=n;i++)
{
scanf("%s",ch),len=strlen(ch);
TreeNodeType *now=root;int pos;
for(int j=;j<len;j++)
{
pos=ch[j]-'a';
if(now->next[pos]==NULL)
{
now->next[pos]=new TreeNodeType,now->next[pos]->id=++tot;
map[tot]=now->next[pos],now->next[pos]->dis=(now->dis*26LL+pos)%mod;
}
vec[i].push_back(now->next[pos]->id),now=now->next[pos];
}
}
int h=,tail=,u,v;que[]=root;
while(h<tail)
{
TreeNodeType *now=que[h++],*temp=NULL;
for(int i=;i<;i++)
{
if(now->next[i]==NULL) continue;
if(now==root) now->next[i]->fail=root;
else
{
temp=now->fail;
while(temp!=NULL)
{
if(temp->next[i]!=NULL)
{
now->next[i]->fail=temp->next[i];
break;
}
temp=temp->fail;
}
if(temp==NULL) now->next[i]->fail=root;
}
que[tail++]=now->next[i];
u=now->next[i]->id,v=now->next[i]->fail->id;
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
}
dfs1(,),dfs2(,);
in(m);int a,a1,b,b1;
for(;m--;)
{
in(a),in(a1),in(b),in(b1);
printf("%lld\n",map[lca(vec[a][a1-],vec[b][b1-])]->dis);
}
return ;
}