14101: 【原4101】Biology

题目描述

author: T 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4101

Description

G博士发现了新的遗传疾病，这种疾病受到多种基因片段的控制。我们用一个仅由小写字母组成的字符串表示一个基因片段，该基因的有效片段为S的所有后缀（包括空串）。根据 G 博士的研究，该遗传疾病的患病概率，与基因的有效片段有关，若控制该遗传疾病的基因片段的共有有效片段越长，则患病概率越大。 G 博士将所有的发现的基因片段放在了一个数据库中，随着研究的进展，G 博士的数据库中储存的基因片段越来越多，这给 G 博士对疾病的研究造成了一定困难。现在 G 博士想知道，对于控制某一疾病的一些基因片段，它们的最长共有有效片段为多长？

Input Format

第一行两个整数N ,M ，其中 N表示数据库中原本存在的基因片段个数，M 表示后来的事件个数。接下来N行，每行一个字符串，表示一个已知的基因片段，其中第i 行的基因片段编号为i。接下来M行，表示M个事件，格式为以下情况之一： 1 . “1 S”，表示发现了一个新的基因片段加入数据库，编号为已有基因片段数+ 1； 2. “2T A1 A2 … … AT”，表示询问编号为 A1 , A2 , … … AT, 这T个编号的最长共有有效片段的长度。

Output Format

对于每个2号操作，输出一行表示最长共有有效片段的长度。

Sample Input

5 5
zzj
pri
prime
ime
owaski
2 3 1 3 5
2 2 2 3
1 actri
2 2 3 4
2 3 2 6 5

Sample Output

Limits

对于前 20 %的数据，N≤ 100，M≤100 ，每段基因片段长度≤100 对于前 50 %的数据，N≤ 10000，M≤10000，每段基因片段长度≤100 接下来 20 %的数据，N≤ 20000，M≤50000，每段基因片段长度≤1000，没有1号操作对于前 100 %的数据， N≤50000 ，M ≤ 100000，2 ≤T ≤10 ，每段基因片段长度≤10000，总字符个数≤1000000 ，数据库中基因型的个数≤100000 不同编号的基因型有可能相同，并且不保证询问不会出现重复元素数据

zqy2018's solution

/*
    See the solution at https://github.com/zqy1018/sjtu_oj_solutions/blob/master/solutions/sjtu4101.md
*/
#include <bits/stdc++.h>
#define INF 2000000000
#define M 100007ull
using namespace std;
typedef unsigned long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, m, tot = 0;
vector<ll> vec[100005];
int lis[15];
char s[10005];
void ins(){
    int l = strlen(s);
    vec[++tot].push_back(0);
    ll lst = 0;
    for (int i = l - 1; i >= 0; --i)
        lst = lst * M + s[i] - 'a', 
        vec[tot].push_back(lst);
}
void init(){
    n = read(), m = read();
    for (int i = 1; i <= n; ++i){
        scanf("%s", s);
        ins();
    }
}
void solve(){
    while (m--){
        int opt = read();
        if (opt == 1){
            scanf("%s", s);
            ins();
        }else {
            int t = read(), mini = INT_MAX;
            for (int i = 1; i <= t; ++i)
                lis[i] = read(), mini = min(mini, static_cast<int>(vec[lis[i]].size()));
            int l = 0, r = mini - 1;
            while (l < r){
                int mid = (l + r + 1) >> 1;
                bool flag = true;
                ll targ = vec[lis[1]][mid];
                for (int i = 2; i <= t; ++i)
                    if (vec[lis[i]][mid] != targ){
                        flag = false;
                        break;
                    }
                if (flag) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", l);
        }
    }
}
int main(){
    init();
    solve();
    return 0;
}