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

5795. 【2018提高组】模拟A组&省选 词典

程序员文章站 2022-04-17 21:37:24
...

Description

5795. 【2018提高组】模拟A组&省选 词典

Input

第一行两个数n,m,表示有n个字符串,m个询问。
接下来n行,每行一个字符串Ti 。
再接下来m行,每行一个字符串Si 。

Output

对于每个询问,输出一个ansi表示答案。

Sample Input

3 2
abcabc
aabc
abbc
aa
ba

Sample Output

1
3

Data Constraint

5795. 【2018提高组】模拟A组&省选 词典
(File IO): input:word.in output:word.out
Time Limits: 1500 ms Memory Limits: 262144 KB

Solution

先对所有的T建立一棵trie
trie上的每个点开一个vector,储存有每一个经过该点的T的编号
对于每个S,在trie上找到对应点
在这个点上利用之前存好的T的编号直接暴力就行了
复杂度与读入复杂度相等

Code1

#include<cstdio> 
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define N 100010
#define M 500010
using namespace std;
int n,m,tot=0,len=0,ans[N],l[M*15],t[M*15],nx[M*15],a[M*15];
char s[N];
struct tire{
    int nx[4];
}tree[M*15];
void add(int x,int y){
    t[++t[0]]=y;
    nx[t[0]]=l[x];
    a[x]=max(a[x],y-t[l[x]]-1);
    l[x]=t[0];
}
void build(char s[],int x){
    int len=strlen(s+1),now=0;
    for(int i=1;i<=len;i++){
        if(!tree[now].nx[s[i]-'a']) tree[now].nx[s[i]-'a']=++tot;
        now=tree[now].nx[s[i]-'a'];
        add(now,x);
    }
}
void find(char s[],int x){
    int len=strlen(s+1),now=0,bz=1;
    for(int i=1;i<=len;i++){
        now=tree[now].nx[s[i]-'a'];
        if(now==0){
            bz=0;
            break;
        }
    }
    if(bz){
        ans[x]=max(a[now],n-t[l[now]]);
    }
}
int main(){
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        build(s,i);
    }
    for(int i=1;i<=m;i++){
        scanf("%s",s+1);
        find(s,i);
    }
    for(int i=1;i<=m;i++){
        if(!ans[i])printf("%d\n",n);else printf("%d\n",ans[i]);
    }
    return 0;
}

Code2

#include<bits/stdc++.h>
#define M 3000005
using namespace std;
char s[100005];
int n,m,cnt=1;
int last[M],ans[M];
int ch[M][3];


void ins(int now)
{
    int p=1;int len=strlen(s);
    for(int i=0;i<len;i++)
    {
        int k=s[i]-'a';
        if(!ch[p][k]) ch[p][k]=++cnt;
        p=ch[p][k];
        ans[p]=max(ans[p],now-last[p]-1);
        last[p]=now;
    } 
}
int ask()
{
    int p=1;int len=strlen(s);
    for(int i=0;i<len and p;i++)
    {
        int k=s[i]-'a';
        p=ch[p][k];
    }
    return max(ans[p],n-last[p]);
}
int main()
{   
    freopen("word.in","r",stdin);
    freopen("word.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%s",s),ins(i);
    for(int i=1;i<=m;i++)
        scanf("%s",s),printf("%d\n",ask());
}


作者:zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/81913702

相关标签: Trie