0分 trie 树求助qwq
查看原帖
0分 trie 树求助qwq
455558
Imiya楼主2022/4/7 21:52

全是 answer too short.

#include<iostream>
#include<vector>
#include<string>
using namespace std;
const int N=1100,M=10100;
int son[M*20][30];
int flg[M*20];
vector<int>ans[M];
int rt,cnt;
void insert(int now,string str,int i,int id){
    if(str.size()==i){
        flg[now]=id;
        return;
    }
    if(!son[now][str[i]-'a'])son[now][str[i]-'a']=++cnt;
    insert(son[now][str[i]-'a'],str,i+1,id);
}
void check(int now,string str,int i,int id){
    if(str.size()==i){
        if(flg[now]&&(ans[flg[now]].empty()||ans[flg[now]].back()!=id))ans[flg[now]].emplace_back(id);
        return;
    }
    if(!son[now][str[i]-'a'])return;
    check(son[now][str[i]-'a'],str,i+1,id);
}
int n,m;
vector<string>essay[N];
void init(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int l;
        cin>>l;
        for(int j=1;j<=l;j++){
            string s;
            cin>>s;
            essay[i].emplace_back(s);
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        insert(rt,s,0,i);
    }
}
int main(){
//    freopen("read.in","r",stdin);
    init();
    for(int i=1;i<=n;i++){
        int l=(int)essay[i].size();
        for(int j=0;j<l;j++)
            check(rt,essay[i][j],0,i);
    }
    for(int i=1;i<=m;i++){
        int l=(int)ans[i].size();
        for(int j=0;j<l-1;j++)
            printf("%d ",ans[i][j]);
        if(l)printf("%d\n",ans[i][l-1]);
        else printf("\n");
    }
    return 0;
}

2022/4/7 21:52
加载中...