题目链接：http://codeforces.com/contest/710/problem/F
题意：维护一个集合，集合要求满足三种操作。 1 str:向集合插入字符串str(保证不会插入之前已经插入过的字符串) 2str:从集合中删除字符串str(保证删除的str一定在集合中) 3 str:str的子串有多少个在集合中出现过。
思路：题目意思就是一个可以插入/删除/查询的AC自动机。但是如果我们暴力求解，每次添加/删除一个字符串到自动机中求从前求一边适配指针的话会TLE。所以我们考虑用其他方法，设置一个恰当的阈值。如果小于这个阈值则把字符串放入trie树中，而大于阈值的直接保存下来。然后对于添加标记+1 ,删除标记-1。关于操作3把字符串分别与字典树的串匹配和保存下来的串匹配。关于在字典树的匹配。我们只需枚举str的所有后缀去匹配字典树即可。对于保存下来的串我们对其每一个建立KMP的next数组，然后就是普通的KMP的单模式匹配了。 用时不到1S
#define _CRT_SECURE_NO_DEPRECATE
#include<stdio.h>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<queue>
#include<math.h>
#include<time.h>
#include<vector>
#include<iostream>
using namespace std;
typedef long long int LL;
const int MAXN = + ;
const int CASE_SIZE = ;
const int S_SIZE = ;
const int B_SIZE = MAXN / S_SIZE + ;
struct Trie{
int child[MAXN][CASE_SIZE], value[MAXN],trieN,root;
void init(){
trieN = root = ; value[root] = ;
memset(child[root], -, sizeof(child[root]));
}
int newnode(){
trieN++; value[trieN] = ;
memset(child[trieN], -, sizeof(child[trieN]));
return trieN;
}
void insert(char *s,int val){
int x = root;
for (int i = ; s[i]; i++){
int d = s[i] - 'a';
if (child[x][d] == -){
child[x][d] = newnode();
}
x = child[x][d];
}
value[x] += val;
}
int search(char *s){
int sum = , x = root;
for (int i = ; s[i]; i++){
int d = s[i] - 'a';
if (child[x][d] == -){
break;
}
x = child[x][d];
sum += value[x];
}
return sum;
}
}trie;
struct KMP{
int Next[MAXN];
void getNext(string s,int len){
memset(Next, , sizeof(Next));
int i = , j = -; Next[] = -;
while (i < len){
if (j == - || s[i] == s[j]){
++i; ++j;
Next[i] = j;
}
else{
j = Next[j];
}
}
}
int search(string s,char *str){
int sum = , j = , lens = s.length(),lenstr=strlen(str);
getNext(s, s.length());
for (int i = ; i < lenstr; i++){
while (j> && s[j] != str[i]){
j = Next[j];
}
if (s[j] == str[i]){
j++;
}
if (j == lens){
sum++; j = Next[j];
}
}
return sum;
}
}kmp;
string Bstr[B_SIZE];
char str[MAXN];
int cnt, Bvalue[B_SIZE];
int main() {
int t, m,len,val;
while (~scanf("%d", &m)) {
trie.init(); cnt = ; memset(Bvalue, , sizeof(Bvalue));
for (int i = ; i <= m; i++){
scanf("%d%s", &t, str);
len = strlen(str);
if (t == || t == ){ //插入和删除
val = (t == ? : -); //插入=1，删除=-1
if (len <= S_SIZE){//小与阈值删除字典树
trie.insert(str, val);
}
else{ //大于阈值直接保存起来
Bstr[cnt] = string(str);
Bvalue[cnt++] = val; //标记是添加的还是删除的
}
}
else{ //查询
LL ans = ;
for (int i = ; i < len; i++){ //字典树上匹配
ans += trie.search(str + i);
}
for (int i = ; i < cnt; i++){ //暴力KMP匹配
if (Bstr[i].length() > len){ continue; }
ans += kmp.search(Bstr[i], str)*Bvalue[i];
}
printf("%I64d\n", ans);
fflush(stdout);
}
}
}
return ;
}