Skip to content

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

0
0
3
1

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;
}