№ |
Отправитель |
Задача |
Язык |
Вердикт |
Время |
Память |
Отослано |
Протест. |
|
98269497 |
Дорешивание:
lszxj |
1437G
- 19
|
GNU C++11
|
Полное решение
|
623 мс
|
53212 КБ
|
2020-11-13 14:54:01 |
2020-11-13 14:54:01 |
|
#include<bits/stdc++.h>
using namespace std;
const int N = 3e5+100;
int n,m,trie[N][26],tot,q[N],fail[N];
int id[N],vv[N],pre[N];
char s[N];
multiset<int>mx[N];
void insert(int k){
int len = strlen(s+1),now = 0;
for(int i = 1; i <= len; i++){
int c = s[i]-'a';
if(!trie[now][c]) trie[now][c]=++tot;
now = trie[now][c];
}
mx[now].insert(0);
id[k] = now;
}
void getfail(){
int l = 1,r = 0;
for(int i = 0; i < 26; i++){
if(trie[0][i]){
q[++r] = trie[0][i];
fail[trie[0][i]] = 0;
}
}
while(l<=r){
int now = q[l];
l++;
if(*mx[fail[now]].rbegin()==-1){
pre[now] = pre[fail[now]];
}else{
pre[now] = fail[now];
}
for(int i = 0; i < 26; i++){
if(trie[now][i]){
q[++r] = trie[now][i];
fail[trie[now][i]] = trie[fail[now]][i];
}else{
trie[now][i] = trie[fail[now]][i];
}
}
}
}
int query(){
int ret = -1,now = 0,len = strlen(s+1);
for(int i = 1; i <= len; i++){
now = trie[now][s[i]-'a'];
for(int j = now; j; j = pre[j])
ret=max(*mx[j].rbegin(),ret);
}
return ret;
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++){
scanf("%s",s+1);
insert(i);
}
fail[0] = 0;
for(int i = 0; i <= tot; i++) mx[i].insert(-1);
getfail();
for(int i = 1; i <= m; i++){
int op,is,v;
scanf("%d",&op);
if(op==1){
scanf("%d%d",&is,&v);
auto w=mx[id[is]].lower_bound(vv[is]);
mx[id[is]].erase(w);
mx[id[is]].insert(v);
vv[is]=v;
}else{
scanf("%s",s+1);
printf("%d\n",query());
}
}
return 0;
}
/*
4 1
a
aa
aaa
aaaa
2 aaaaaaaaaaaaaaaa
*/
Время: ? ms, память: ? КБ