NOIP2017提高A组模拟10.6】Biology

题目

trie

暴力就是对于每个询问的T个字符串
第i个和第i+1个直接个从后暴力枚举每位是否相同，
但这个方法TLE
我们考虑是否可以用更快的方法来求出两个字符串的最长公共后缀。
我们把所有的字符串从后往前扔进trie中，搞个lca就可以了，最长公共后缀就是lca的深度。

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
const int maxlongint=2147483647;
const int mo=1e9+7;
const int N=1000105;
using namespace std;
struct trie
{
    int a[27],deep;
}tr[N];
int n,m,ans,rt[N],tot,len,le,g[N][23],lo;
char s[N];
int lca(int x,int y)
{
    if(tr[x].deep>tr[y].deep) swap(x,y);
    for(int j=lo;j>=0;j--)
        if(tr[g[y][j]].deep>=tr[x].deep) y=g[y][j];
    if(x==y) return tr[x].deep;
    for(int j=lo;j>=0;j--)
        if(g[y][j]!=g[x][j]) x=g[x][j],y=g[y][j];
    return tr[g[x][0]].deep;
}
int put(int x)
{
    int now=1;
    for(int i=x;i>=1;i--)
    {
        int t=tr[now].a[s[i]-'a'];
        if(t) now=t;
        else 
        {
            tr[tr[now].a[s[i]-'a']=++tot].deep=tr[now].deep+1,g[tot][0]=now,now=tot;
            for(int j=1;j<=lo;j++) g[now][j]=g[g[now][j-1]][j-1];
        }
    }
    return now;
}
int main()
{
    scanf("%d%d",&n,&m);
    lo=20;
    tr[++tot].deep=1;
    for(int i=1;i<=n;i++)
    {
        scanf("%s",s+1);
        int len=strlen(s+1);
        rt[i]=put(len);
    }
    for(int i=1;i<=m;i++)
    {
        int t;
        scanf("%d",&t);
        if(t==1)
        {
            scanf("%s",s+1);
            int len=strlen(s+1);
            rt[++n]=put(len);
        }
        else
        {
            int T,TU[12],ans=maxlongint;
            scanf("%d",&T);
            for(int j=1;j<=T;j++) scanf("%d",&TU[j]);
            for(int j=1;j<=T-1;j++) ans=min(lca(rt[TU[j]],rt[TU[j+1]]),ans);
            printf("%d\n",ans-1);
        }
    }
}