BZOJ2746: [HEOI2012]旅行问题(AC自动机 LCA)

Time Limit: 30 Sec  Memory Limit: 256 MB

Submit: 1188  Solved: 383

[Submit][Status][Discuss]

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。 

Source

想骂人,。。。。

这题我一开始按fail图做的,然后死活90分,调了一下午,心态爆炸。。

说出来泥萌可能不信,如果我要是在2012年以前出生,这题可能就是我出的了qwq。。

刚学完AC自动机的时候我就感觉能在AC自动机的fail树上搞事情,比如求个lca啊,询问个路径和啊,断开一条边啊之类的。

然后我自己证了一个多小时,得到一条性质:

点$x$与点$y$在$fail$树中$lca$处的到的字符串,为模式串中与$x,y$公共后缀最长的前缀

本来想把这题出出来着,结果百度了一下:fail树+lca,正好找到这题,mmp,,

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
using namespace std;
const int MAXN = 1 << 20, mod = 1000000007;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N;
char s[MAXN]; 
int ch[MAXN][26], root = 0, tot = 0;
int bg[MAXN], pos[MAXN << 1], cnt = 0, fa[MAXN][21], deep[MAXN];;
long long  val[MAXN];
void insert(char *s, int ID) {
     bg[ID] = cnt;
    int N = strlen(s + 1);
    int now = root;
    for(int i = 1; i <= N; i++) {
        int x = s[i] - 'a';
        if(!ch[now][x]) ch[now][x] = ++tot;
        val[ch[now][x]] = ((val[now] * 26) % mod + x % mod) % mod;
        now = ch[now][x];
        pos[++cnt] = now;
    }
}
vector<int> v[MAXN];
void GetFail() {
    queue<int> q; 
    deep[root] = 1; 
    //for(int i = 0; i <= tot; i++) fail[i] = 1;
    fa[root][0] = 1;
    for(int i = 0; i < 26; i++) if(ch[root][i]) q.push(ch[root][i]), fa[ch[root][i]][0] = 1;
    while(!q.empty()) {
        int p = q.front(); q.pop();
        if(p != 1) deep[p] = deep[fa[p][0]] + 1;
        for(int i = 0; i < 26; i++) {
            if(ch[p][i]) {
                int t = p;
                for(t = fa[p][0]; t != 1 && !ch[t][i]; t = fa[t][0]);
                if(ch[t][i]) fa[ch[p][i]][0] = ch[t][i];
                else  fa[ch[p][i]][0] = 1;
                //fa[ch[p][i]][0] = ch[fa[p][0]][i],
                 q.push(ch[p][i]);
            }
                
        }
    }
}
void Pre() {
    for(int i = 1; i < 21; i++) 
        for(int j = 0; j <= tot; j++)    
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
}
int LCA(int x, int y) {
    if(deep[x] < deep[y]) swap(x, y);
    for(int i = 20; i >= 0; i--) 
        if(deep[fa[x][i]] >= deep[y])
            x = fa[x][i];
    if(x == y) return x;
    for(int i = 20; i >= 0; i--)
        if(fa[x][i] != fa[y][i])
            x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}
main() {
#ifdef WIN32
    freopen("a.in", "r", stdin);
//    freopen("a.out", "w", stdout);
#endif
    N = read();
    for(int i = 1; i <= N; i++) scanf("%s", s + 1), insert(s, i);
    GetFail(); Pre();
    int Q = read();
    while(Q--) {
        int S1 = read(), L1 = read(), S2 = read(), L2 = read();
        int ans = LCA(pos[bg[S1] + L1], pos[bg[S2] + L2]);
        printf("%lld\n", val[ans]);
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

Codeforces Round #395 (Div. 2)(A.思维,B,水)

A. Taymyr is calling you time limit per test:1 second memory limit per test:256 ...

3016
来自专栏菩提树下的杨过

javascript:查找“跳号”号码

业务背景: 航空货运系统中,“货运代理商”会定期从“航空公司”领取一定数量的纸质运单(每张纸上有一个单号),这些单号都是连续的(即:每次可以理解为领取一个“号段...

1958
来自专栏ml

初学java之try-catch-finally语句的实例

1 /* 2 try - catch语句的例子,模拟向货船上装载集装箱 3 ,如果货船超重,那么货船认为这是一个异常,将拒绝装载集装箱, 4...

3589
来自专栏个人分享

Hive metastore源码阅读(二)

  最近随着项目的深入,发现hive meta有些弊端,就是你会发现它的元数据操作与操作物理集群的代码耦合在一起,非常不利于扩展。比如:在create_tabl...

1783
来自专栏数据结构与算法

08:病人排队

08:病人排队 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 病人登记看病,编写一个程序,将登记的病人按照以下原则排出看...

3146
来自专栏小樱的经验随笔

BZOJ 3038: 上帝造题的七分钟2【线段树区间开方问题】

3038: 上帝造题的七分钟2 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 1469  Solved: 63...

2624
来自专栏古时的风筝

模拟实现Spring中的注解装配

在Spring中,XML文件中的bean配置是实现Spring IOC的核心配置文件,在早版本的Spring中,只能基于XML配置文件,配置各个对象之间的依赖关...

2235
来自专栏mwangblog

python类(二)

1262
来自专栏对角另一面

lodash源码分析之baseFindIndex中的运算符优先级

本文为读 lodash 源码的第十篇,后续文章会更新到这个仓库中,欢迎 star:pocket-lodash

2008
来自专栏云时之间

数据结构(三):栈与队列

3.1❶若按教科书3.1.1节中图3.1(b)所示铁道进行车厢调度(注意:两侧铁道均为单向行驶道),则请回答: ? (1) 如果进站的车厢序列为123,则可能...

3627

扫码关注云+社区

领取腾讯云代金券