「bsoj5137」基因 - trie树+LCA

题目大意

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

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

---

题目分析

发现题目的插入操作件没啥用。
将字符串翻转一下，把后缀变为前缀，接下来的就好处理了。
对所有字符串建成trie树，题目要求的$LCP$即为trie树上的$LCA$，因为$T\le10$，故可以两两求$LCA$。

求$LCA$可以使用倍增，只需要动态预处理稀疏表即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=150005,maxc=1000005;

int father[maxc],p[maxc][25],Depth[maxc];

void Sparse_Table(int x) {
	p[x][0]=father[x];
	for(int j=1; j<=log2(x); j++)
		if(p[x][j-1]!=-1)p[x][j]=p[p[x][j-1]][j-1];
}
int LCA(int a,int b) {
	if(Depth[a]<Depth[b])swap(a,b);
	int k=log2(Depth[a]);
	for(int i=k; i>=0; i--) {
		if(Depth[a]==Depth[b])break;
		if(Depth[a]-(1<<i)>=Depth[b])a=p[a][i];
	}
	if(a==b)return b;
	for(int i=k; i>=0; i--)
		if(p[a][i]!=-1&&p[a][i]!=p[b][i]) {
			a=p[a][i];
			b=p[b][i];
		}
	return p[a][0];
}

struct Tree {
	int child[27];
	void clear() {
		memset(child,0,sizeof(child));
	}
};

struct Trie {
	Tree tree[maxc];
	int cnt;
	void init() {
		cnt=0;
		memset(tree,0,sizeof(tree));
	}
	int insert(string s) {
		reverse(s.begin(),s.end());
		int x=0;
		for(int i=0; i<s.length(); i++) {
			int y=s[i]-'a';
			if(tree[x].child[y]==0) {
				tree[x].child[y]=++cnt;
				father[cnt]=x;
				Depth[cnt]=Depth[x]+1;
				Sparse_Table(cnt);
			}
			x=tree[x].child[y];
		}
		return x;
	}
} trie;

int n,m,M[maxn],cnt=0;

int main() {
	n=Get_Int();
	m=Get_Int();
	memset(p,-1,sizeof(p));
	for(int i=1; i<=n; i++) {
		char s[10005];
		scanf("%s",s);
		M[++cnt]=trie.insert(s);
	}
	for(int i=1; i<=m; i++) {
		int opt=Get_Int();
		if(opt==1) {
			char s[10005];
			scanf("%s",s);
			M[++cnt]=trie.insert(s);
		} else {
			int t=Get_Int(),lca=M[Get_Int()];
			for(int i=2; i<=t; i++) {
				int x=Get_Int();
				lca=LCA(lca,M[x]);
			}
			printf("%d\n",Depth[lca]);
		}
	}
	return 0;
}