欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP2017提高A组模拟10.6】Biology

程序员文章站 2023-12-24 22:21:33
...

题目

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);
        }
    }
}

上一篇:

下一篇: