当前位置:网站首页>[dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
[dictionary tree] [trie] p3879 [tjoi2010] reading comprehension
2022-07-06 07:23:00 【Chasing the beacon】
P3879 [TJOI2010] reading comprehension
Dictionary tree writing
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
int nex[300007][26],n,cnt=0;
bitset<1001> b[500007];//bool b[500007][1001];
void insert(char* s,int rol){
int len=strlen(s+1);
int now=0;
FOR(i,1,len){
int p=s[i]-'a';
if(!nex[now][p])// If $Trie$ The tree is numbered without the prefix of this word
nex[now][p]=++cnt;// The number mentioned above
now=nex[now][p];// Then go deeper , Update the current location
}
b[now][rol]=1;// This word is in the x There's a line
}
void check(char* s){
int len=strlen(s+1);
int now=0,flag=1;
FOR(i,1,len){
int p=s[i]-'a';
if(!nex[now][p]){
// If in Trie There is no current character in the tree , You can do it directly break It fell off
flag=0;
break;
}
now=nex[now][p];// Otherwise, update the location
}
if(flag){
FOR(i,1,n)// On the surface of the question, it is said to output in dictionary order
if(b[now][i]) cout<<i<<" ";// In which sentences does the output appear
}
putchar('\n');
}
int main(){
cin>>n;
char s[25];
FOR(i,1,n){
int l;cin>>l;
FOR(j,1,l){
// Word by word insertion Trie In the tree
cin>>(s+1);
insert(s,i);
}
}
int m;cin>>m;
FOR(i,1,m){
cin>>(s+1);
check(s);
}
return 0;
}
STL: MAP + VECTOR How to write it
use STL
You don't have to worry about how big the array is and how big the space is , But it will take more time
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define mem(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn = 100001;
int n,m,num,cnt[maxn];
string s;
map<string,vector<int> >a;
int main(){
cin>>n;
FOR(i,1,n){
cin>>num;
FOR(j,1,num){
cin>>s;
a[s].push_back(i);// Every word is a vector, Save the number of sentences
}
}
cin>>m;
FOR(i,1,m){
cin>>s;
mem(cnt);//cnt Is to remove the heavy bucket . Every time you use it to output different queries, you need to clear .
int len=a[s].size();
FOR(j,0,len-1)
if(cnt[a[s][j]] == 0){
cout<<a[s][j]<<" ";
cnt[a[s][j]]++;// Remove weight with bucket
}
cout<<endl;
}
return 0;
}
STL: MAP + SET How to write it
use set
It can automatically remove the weight , More convenient . meanwhile Time consuming is excellent , Second only to handwriting Trie
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
using namespace std;
map<string,set<int> > m;
int main(){
int n,p,l;
string s;
cin>>n;
FOR(i,1,n){
cin>>l;// The number of words
FOR(j,0,l-1){
cin>>s;// word
m[s].insert(i);
}
}
cin>>p;
while(p--){
cin>>s;
if(m.count(s)){
// If m There are elements in s
for(auto iter=m[s].begin();iter!=m[s].end();++iter)
cout<<*iter<<" ";
}
cout<<endl;
}
return 0;
}
边栏推荐
猜你喜欢
Detailed explanation | detailed explanation of internal mechanism of industrial robot
leetcode841. Keys and rooms (medium)
杰理之BLE【篇】
SSM learning
Ble of Jerry [chapter]
【MySQL学习笔记32】mvcc
navicat如何导入MySQL脚本
Lesson 12 study notes 2022.02.11
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
随机推荐
word中如何删除某符号前面或后面所有的文字
OpenJudge NOI 2.1 1661:Bomb Game
Seriously recommend several machine learning official account
Upgraded wechat tool applet source code for mobile phone detection - supports a variety of main traffic modes
Jerry's general penetration test - do data transmission with app Communication [article]
Lesson 12 study notes 2022.02.11
Ble of Jerry [chapter]
word中把帶有某個符號的行全部選中,更改為標題
Leetcode59. spiral matrix II (medium)
Go learning --- use reflection to judge whether the value is valid
[MySQL learning notes 30] lock (non tutorial)
ORACLE列转行--某字段按指定分隔符转多行
Leetcode 78: subset
Openjudge noi 2.1 1749: Digital Square
超级浏览器是指纹浏览器吗?怎样选择一款好的超级浏览器?
If Jerry needs to send a large package, he needs to modify the MTU on the mobile terminal [article]
Supervisor usage document
Uni app third party package configuration network request
Word setting directory
OpenJudge NOI 2.1 1661:Bomb Game