General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
98269497 Practice:
lszxj
1437G - 19 GNU C++11 Accepted 623 ms 53212 KB 2020-11-13 14:54:01 2020-11-13 14:54:01
→ Source
#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
*/
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details