# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
114113312 |
Practice:
vjudge1 |
1437G
- 19
|
C++17 (GCC 7-32)
|
Accepted
|
1403 ms
|
53788 KB
|
2021-04-24 15:49:14 |
2021-04-24 15:49:14 |
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int trie[303030][26],belong[303030],fail[303030],tot=0,rt=0,orw[303030];
multiset<int> w[303030];
int n,m;
char s[303030];
int clrsta[303030],top=0;int vis[303030];
inline void build(){
queue<int> q;
for(int i=0;i<26;++i){
if(trie[rt][i]){
fail[trie[rt][i]]=rt;
q.push(trie[rt][i]);
}
}
while(q.size()){
int u=q.front();q.pop();
for(int i=0;i<26;++i){
if(trie[u][i]){
fail[trie[u][i]]=trie[fail[u]][i];
q.push(trie[u][i]);
}else{
trie[u][i]=trie[fail[u]][i];
}
}
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1,len,cur;i<=n;++i){
scanf("%s",s+1);
len=strlen(s+1);
cur=rt;
for(int j=1;j<=len;++j){
if(!trie[cur][s[j]-'a'])trie[cur][s[j]-'a']=++tot;
cur=trie[cur][s[j]-'a'];
}
belong[i]=cur;
w[cur].insert(0);
}
build();
for(int i=1,op;i<=m;++i){
scanf("%d",&op);
if(op==1){
int i,x;
scanf("%d%d",&i,&x);
w[belong[i]].erase(w[belong[i]].find(-orw[i]));
w[belong[i]].insert(-x);
orw[i]=x;
}else{
scanf("%s",s+1);
int len=strlen(s+1);
int cur=rt,cpcur;
int ans=-1;
for(int j=1;j<=len;++j){
cpcur=cur=trie[cur][s[j]-'a'];
while(!vis[cpcur]){
if(w[cpcur].size())ans=max(ans,-*(w[cpcur].begin()));
vis[cpcur]=1;
clrsta[++top]=cpcur;
cpcur=fail[cpcur];
}
}
printf("%d\n",ans);
while(top)vis[clrsta[top--]]=0;
}
}
}
Click to see test details