5795. 【2018提高组】模拟A组&省选 词典
程序员文章站
2022-04-17 21:37:24
...
Description
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
(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