Skip to content

1148: Biology

题目

题目描述

G博士发现了新的遗传疾病,这种疾病受到多种基因片段的控制。

我们用一个仅由小写字母组成的字符串 表示一个基因片段,该基因的有效片段为S的所有后缀(包括空串)。

根据 G 博士的研究,该遗传疾病的患病概率,与基因的有效片段有关,若控制该遗传疾病的基因片段的共有有效片段越长,则患病概率越大。

G 博士将所有的发现的基因片段放在了一个数据库中,随着研究的进展,G 博士的数据库中储存的基因片段越来越多,这给 G 博士对疾病的研究造成了一定困难。

现在 G 博士想知道,对于控制某一疾病的一些基因片段,它们的最长共有有效片段为多长?

输入格式

第一行两个整数N ,M ,其中 N表示数据库中原本存在的基因片段个数,M 表示后来的事件个数。

接下来N行,每行一个字符串,表示一个已知的基因片段,其中第i 行的基因片段编号为i。

接下来M行,表示M个事件,格式为以下情况之一:

  1. “1 S”,表示发现了一个新的基因片段加入数据库,编号为已有基因片段数+ 1;
  2. “2T A1 A2 … … AT”,表示询问编号为 A1 , A2 , … … AT, 这T个编号的最长共有有效片段的长度。

输出格式

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

样例输入

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

样例输出

0
0
3
1

数据范围

对于前 20 %的数据,$N\leq 100$,$M\leq 100$,每段基因片段长度$\leq100$

对于前 50 %的数据,$N\leq 10000$,$M\leq10000$,每段基因片段长度$\leq100$

接下来 20 %的数据,$N\leq20000$,$M\leq50000$,每段基因片段长度$\leq1000$,没有1号操作

对于前 100 %的数据, $N\leq50000$ ,$M \leq100000$,$2 \leq T \leq10$ ,每段基因片段长度$\leq10000$,总字符个数$\leq1000000$ ,数据库中基因型的个数$\leq100000$

不同编号的基因型有可能相同,并且不保证询问不会出现重复元素数据

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!