旅行问题（bzoj 2746）

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后输出:
a->0
b->1
.
.
.
z->25
比如地区cab被编码成2 * 26? + 0 * 26? + 1 * 26? = 1353。

Input

第一行给定一个整数n
第2…n+1行:每i+1行给定一个字符串a[i],表示第i个描述。
接下来一行一个整数m
接下来m行:每行给定四个整数i,j,k,l，字母含义与题目描述一致。

Output

共m行，每行一个整数，表示答案字符串的编码。

Sample Input

2
aabb babb
2
1 3 2 3
1 4 2 4

Sample Output

1
1
【样例说明】
询问1中的公共后缀有ab和b，但是没有ab这个地区，只有b地区，所以只能选择b这个地区；
询问2中的公共后缀有abb、bb和b，但是没有abb和bb这两个地区，只有b地区，所以只能选择b这个地区。

HINT

【数据范围】

设这个国家地区总数数为tot（注意：输入的字符串总长度可能超过tot！）对于30%的数据，满足tot，m，n<=100；

对于50%的数据，满足tot，m，n<=1000；

对于80%的数据，满足tot，m，n<=100000；

对于100%的数据，满足tot，m，n<=1000000；

保证输入文件不超过20MB。

/*

    题面较难理解，意思就是求两个字符串的前缀的最长后缀，且这个后缀在所有的字符串中曾经出现过。

    这个题目完美符合了fail树的最近公共祖先的定义。

    因为它们的公用祖先一定是各自的后缀，且一定是最长的。

*/

#include<cstdio>

#include<iostream>

#include<queue>

#include<cstring>

#define N 1000010

#define mod 1000000007

#define lon long long

using namespace std;

int a[N][],fa[N][],dep[N],sum[N],pos[N*],st[N],n,m,size=,tot;

char s[N];

queue<int> q;

void insert(int id){

    int len=strlen(s),now=;st[id]=tot;

    for(int i=;i<len;i++){

        int t=s[i]-'a';

        if(!a[now][t]){

            a[now][t]=++size;

            sum[size]=((lon)sum[now]*+t)%mod;

        }

        now=a[now][t];

        pos[++tot]=now;

    }

}

void build(){

    q.push();

    while(!q.empty()){

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

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

            if(!a[now][i]) continue;

            int k=fa[now][];

            while(!a[k][i]) k=fa[k][];

            fa[a[now][i]][]=a[k][i];

            dep[a[now][i]]=dep[a[k][i]]+;

            q.push(a[now][i]);

        }

    }

}

void get_fa(){

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

        for(int i=;i<=size;i++)

            fa[i][j]=fa[fa[i][j-]][j-];

}

int LCA(int u,int v){

    if(dep[u]<dep[v]) swap(u,v);

    int t=dep[u]-dep[v];

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

        if(t&(<<i)) u=fa[u][i];

    if(u==v) return u;

    for(int i=;i>=;i--)

        if(fa[u][i]!=fa[v][i]){

            u=fa[u][i];

            v=fa[v][i];

        }

    return fa[u][];

}

int main(){

    for(int i=;i<;i++) a[][i]=;

    scanf("%d",&n);

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

        scanf("%s",s);

        insert(i);

    }

    build();get_fa();

    scanf("%d",&m);

    for(int i=;i<=m;i++){

        int x1,x2,y1,y2;

        scanf("%d%d%d%d",&x1,&x2,&y1,&y2);

        int anc=LCA(pos[st[x1]+x2],pos[st[y1]+y2]);

        printf("%d\n",sum[anc]);

    }

    return ;

}

巴特西