Description

Input

Output

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

Data Constraint

Hint

zzj，prime，owaski三種基因片段的最長(zhǎng)共有有效片段為空
pri，prime兩種基因片段的最長(zhǎng)共有效片段為空
添加基因片段actri，編號(hào)為6
prime，ime兩種基因片段的最長(zhǎng)共有有效片段為ime
pri，actri，owaski三種基因片段的最長(zhǎng)共有有效片段i

Solution

• 這題是 Trie+Lca 的經(jīng)典題。

• 對(duì)于加入的每個(gè)字符串，倒序放入一個(gè) Trie 中，記錄其最終節(jié)點(diǎn)、深度、倍增ST表等信息。

• 那么對(duì)于查詢的那幾個(gè)串，只需求出它們?cè)?Trie 上的 Lca 即可，答案即為 Lca 深度。

• 時(shí)間復(fù)雜度 O(M?T?log?Len) 。

Code

#include<cstdio> #include<algorithm> #include<cmath> using namespace std; const int N=1e5+2,M=N*10; int len,tot; int s[M],w[N],p[N],g[M][26]; int f[M][20],dep[M],a[10]; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } inline int write(int x) {if(x>9) write(x/10);putchar(x%10+'0'); } inline void insert(int x) {char ch=getchar();while(ch<'a' || ch>'z') ch=getchar();while(ch>='a' && ch<='z') s[++len]=ch-'a',ch=getchar();w[x+1]=len+1; } inline void trie(int x) {int num=0;for(int i=w[x+1]-1;i>=w[x];i--){if(!g[num][s[i]]){g[num][s[i]]=++tot;dep[tot]=dep[num]+1;f[tot][0]=num;for(int j=1;j<20;j++) f[tot][j]=f[f[tot][j-1]][j-1];}num=g[num][s[i]];}p[x]=num; } inline int lca(int x,int y) {if(dep[x]<dep[y]) swap(x,y);for(int i=log2(dep[x]);i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];if(x==y) return x;for(int i=log2(dep[x]);i>=0;i--)if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];return f[x][0]; } int main() {int n=read(),m=read();for(int i=w[1]=1;i<=n;i++){insert(i);trie(i);}while(m--){int op=read();if(op==1){insert(++n);trie(n);}else{int t=read();for(int i=0;i<t;i++) a[i]=read();sort(a,a+t);t=unique(a,a+t)-a;int ans=p[a[0]];for(int i=1;i<t;i++) ans=lca(ans,p[a[i]]);write(dep[ans]),putchar('\n');}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的JZOJ 5397. 【NOIP2017提高A组模拟10.6】Biology的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。