我们将所有字符串(包括新加的)全部离线倒着加到一个Trie里，然后发现几个串的 第一个字符在Trie中的位置 的LCA的深度即为每个询问的答案，由于LCA满足结合律，一一合并即可
注意数组的大小
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long
#define db double
#define FN2 "biology"
const int logs = 20;
struct note {
int fa;
int ch[26];
int pre[logs + 1];
int dep;
}tree[1000000 + 5];
int tb, n, m, wz[100000 + 5], cx[100000 + 5][10 + 5], ctot;
char s[10000 + 5];
void insert(char *s, int a, int c, int xh) {
if (tree[c].ch[s[a] - 'a'] == 0) tree[c].ch[s[a] - 'a'] = ++tb, tree[tb].fa = c;
if (a == 0) wz[xh] = tree[c].ch[s[a] - 'a']; else insert(s, a - 1, tree[c].ch[s[a] - 'a'], xh);
}
void dfs(int u, int pa) {
tree[u].dep = tree[pa].dep + 1;
tree[u].pre[0] = pa;
for (int i = 1; i <= logs; i++) tree[u].pre[i] = tree[tree[u].pre[i - 1]].pre[i - 1];
for (int i = 0; i < 26; i++)
if (tree[u].ch[i] != 0) dfs(tree[u].ch[i], u);
}
int getlca(int a, int b) {
if (tree[a].dep < tree[b].dep) swap(a, b);
for (int i = logs; i >= 0; i--) if (tree[tree[a].pre[i]].dep >= tree[b].dep) a = tree[a].pre[i];
if (a == b) return a;
for (int i = logs; i >= 0; i--) if (tree[a].pre[i] != tree[b].pre[i]) a = tree[a].pre[i], b = tree[b].pre[i];
return tree[a].pre[0];
}
void clean() {
tb = 1, ctot = 0;
for (int i = 1; i <= 1000000 + 3; i++) {
tree[i].dep = 0, tree[i].fa = 0;
for (int j = 0; j < 26; j++) tree[i].ch[j] = 0, tree[i].pre[j] = 0;
}
}
void solve() {
clean();
for (int i = 1; i <= n; i++) {
scanf("%s", s); int len = strlen(s);
insert(s, len - 1, 1, i);
}
for (int i = 1; i <= m; i++) {
int opt; scanf("%d", &opt);
if (opt == 1) {
scanf("%s", s); int len = strlen(s);
insert(s, len - 1, 1, ++n);
} else {
ctot++;
scanf("%d", &cx[ctot][0]);
for (int j = 1; j <= cx[ctot][0]; j++) scanf("%d", &cx[ctot][j]);
}
}
dfs(1, 0);
for (int i = 1; i <= ctot; i++) {
int lca = wz[cx[i][1]];
for (int j = 2; j <= cx[i][0]; j++) {
lca = getlca(lca, wz[cx[i][j]]);
}
printf("%d\n", tree[lca].dep - 1);
}
}
int main() {
freopen(FN2".in", "r", stdin);freopen(FN2".out", "w", stdout);
scanf("%d%d", &n, &m), solve();
fclose(stdin), fclose(stdout);
return 0;
}
题目描述
G 博士发现了新的遗传疾病，这种疾病受到多种基因片段的控制。
我们用一个仅由小写字母组成的宇符串S表示一个基因片段，该基因的有效片段为S的所有后缀(包括空串)。
根据G 博士的研究,该遗传疾病的患病概率，与基因的有效片段有关，若控制该遗传疾病的基因片段的共有有效片段越长，则患病概率越大。
G 博士将所有的发现的基因片段放在了一个数据库中，随着研究的进展，G 博士的数据库中储存的基因片段越来越多，这给G 博士对疾病的研究造成了一定困难。
现在G 博士想知道，对于控制某一疾病的一些基因片段，它们的最长共有有效片段为多长?
Input
第一行两个整数N,M,其中N表示数据库中原本存在的基因片段个数，M表示后来的事件个数
接下来N行,每行一个字符串，表示一个已知的基因片段，其中第i行的基因片段编号为i
接下来M行，表示M个事件，格式为以下情况之一:
1.”1 S”,表示发现了一个新的基因片段加入数据库，编号为已有基因片段数+1
2.“2 T A1 A2 .. AT“表示询问编号为A1,A.,….AT这T个编号的最长共有有效片段的长度
𝟓 𝟓
𝒛𝒛𝒋
𝒑𝒓𝒊
𝒑𝒓𝒊𝒎𝒆
𝒊𝒎𝒆
𝒐𝒘𝒂𝒔𝒌𝒊
𝟐 𝟑 𝟏 𝟑 𝟓
𝟐 𝟐 𝟐 𝟑
𝟏 𝒂𝒄𝒕𝒓𝒊
𝟐 𝟐 𝟑 𝟒
𝟐 𝟑 𝟐 𝟔 𝟓
Output
对于每个2号操作，输出一行表示最长共有有效片段的长度
𝟎
𝟎
𝟑
𝟏
对于前30%的数据，$N \leq 100, M \leq 100,$每段基因片段长度$S \leq 100$
对于前50%的数据，$N \leq 10000,M \leq 10000$,每段基因片段长度$\leq 100$
接下来20%的数据，$N \leq 20000,M \leq 50000$,每段基因片段长度$\leq 1000$,没有1号操作
对于前100%的数据，$N \leq 50000,M \leq 100000,2 \leq T \leq 10,$每段基因片段长度$\leq 10000$, 总字符个数$ \leq 1000000$,数据库中基因型的个数$\leq 100000$
不同编号的基因型有可能相同，并且不保证询问不会出现重复元素
数据虽然不是完全随机，但依然保留水的本质
Hint
𝒛𝒛𝒋，𝒑𝒓𝒊𝒎𝒆，𝒐𝒘𝒂𝒔𝒌𝒊三种基因片段的最长共有有效片段为空
𝒑𝒓𝒊，𝒑𝒓𝒊𝒎𝒆两种基因片段的最长共有效片段为空
添加基因片段𝒂𝒄𝒕𝒓𝒊，编号为𝟔
𝒑𝒓𝒊𝒎𝒆，𝒊𝒎𝒆两种基因片段的最长共有有效片段为𝒊𝒎𝒆
𝒑𝒓𝒊，𝒂𝒄𝒕𝒓𝒊，𝒐𝒘𝒂𝒔𝒌𝒊三种基因片段的最长共有有效片段𝒊
