P 3879阅读理解

点击查看代码

#include<bits/stdc++.h>using namespace std;const int N=5e6,M=1e3+10;int son[N][26];
char str[21];
//这个bitset变量实际上就是集合的一种变形，实现了一个二维数组，映射起来有点麻烦，/但是内存就是优点
bitset<M> bs[N];
int n,m,idx;
//对每一个单词进行读入，因此最后的p就是单词的末尾
inline void insert(char* str,int x)
{int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!son[p][u]) son[p][u]=++idx;p=son[p][u];}bs[p][x]=1;}inline void query(char* str)
{int p=0;for(int i=0;str[i];i++){int u=str[i]-'a';if(!son[p][u]){cout<<' '<<endl;return;}p=son[p][u];}for(int i=1;i<=n;i++){if(bs[p][i]==1) cout<<i<<" ";}cout<<endl;
}int main()
{cin>>n;//用迭代时因为还需要记录是第几篇文章for(int i=1;i<=n;i++){int len;cin>>len;//对每一段每一个单词进行读入for(int j=1;j<=len;j++){cin>>str;insert(str,i);}}cin>>m;while(m--){cin>>str;query(str);}return 0;
}依旧是简单的模板题目，不过这里强化了我对insert操作的认知，每次最后的p就是末尾，给这个末尾++就相当于记录，基本上所有的操作都是在单词末尾进行
而且加强了我对内存的认知，1mb=1e6字节，bitset<>[]是实现映射又节省内存的方法
以及如果要记得n处理的第几个的话应该用for，因为这样可以对每一个i操作