# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
96946369 |
Practice:
Nerovix |
1437G
- 15
|
C++17 (GCC 7-32)
|
Accepted
|
966 ms
|
54216 KB
|
2020-10-28 02:56:23 |
2020-10-28 10:27:07 |
|
#include<bits/stdc++.h>
using namespace std;
const int maxn=300005;
int ch[maxn][26],fail[maxn],cnt;
int top[maxn],n,m,tg[maxn];
int ep[maxn],v[maxn],val[maxn];
multiset<int>s[maxn];
int main(){
ios::sync_with_stdio(0);
cin>>n>>m;
memset(val,-1,sizeof val);
for(int i=1;i<=n;i++){
string str;
cin>>str;
int u=0;
for(auto x:str){
u=ch[u][x-'a']?ch[u][x-'a']:(ch[u][x-'a']=++cnt);
}
ep[i]=u;
s[u].insert(0);
val[u]=0;
tg[u]=1;
}
queue<int>q;
tg[0]=1;
top[0]=0;
for(int i=0;i<26;i++){
if(ch[0][i]){
fail[ch[0][i]]=0;
if(tg[fail[ch[0][i]]])
top[ch[0][i]]=fail[ch[0][i]];
else top[ch[0][i]]=top[fail[ch[0][i]]];
q.push(ch[0][i]);
}
}
while(q.size()){
int x=q.front();
q.pop();
for(int i=0;i<26;i++){
if(ch[x][i]){
fail[ch[x][i]]=ch[fail[x]][i];
if(tg[fail[ch[x][i]]])
top[ch[x][i]]=fail[ch[x][i]];
else top[ch[x][i]]=top[fail[ch[x][i]]];
q.push(ch[x][i]);
}
else{
ch[x][i]=ch[fail[x]][i];
}
}
}
while(m--){
int op,i,x;string q;
cin>>op;
if(op==1){
cin>>i>>x;
int u=ep[i];
s[u].erase(s[u].find(v[i]));
v[i]=x;
s[u].insert(x);
val[u]=*s[u].rbegin();
}
else{
int ans=-1;
cin>>q;
int u=0;
for(auto x:q){
u=ch[u][x-'a'];
for(int v=u;v;v=top[v])
ans=max(ans,val[v]);
}
cout<<ans<<"\n";
}
}
}
Click to see test details