Problem Description
度熊手上有一本神奇的字典,你可以在它裡面做如下三個操作:
1、insert : 往神奇字典中插入一個單詞
2、delete: 在神奇字典中删除所有字首等于給定字元串的單詞
3、search: 查詢是否在神奇字典中有一個字元串的字首等于給定的字元串
Input
N(1≤N≤100000),代表度熊對于字典的操作次數,接下來
N行,每行包含兩個字元串,中間中用空格隔開。第一個字元串代表了相關的操作(包括: insert, delete 或者 search)。第二個字元串代表了相關操作後指定的那個字元串,第二個字元串的長度不會超過30。第二個字元串僅由小寫字母組成。
Output
對于每一個search 操作,如果在度熊的字典中存在給定的字元串為字首的單詞,則輸出Yes 否則輸出 No。
Sample Input
5
insert hello
insert hehe
search h
delete he
search hello
Sample Output
Yes
No
#include<cstdio>
#include<string>
#include<map>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn = 50;
const int maxp = 3e6 + 5;
char s[maxn], x[maxn];
int n, tot, cnt[maxp];
int f[maxp][26];
int main()
{
while (scanf("%d", &n) != EOF)
{
tot = 1; cnt[1] = 0; memset(f[0], 0, sizeof(f[0]));
while (n--)
{
scanf("%s%s", s, x);
if (s[0] == 'i')
{
int rt = 1;
for (int i = 0,j; x[i]; i++)
{
j = x[i] - 'a';
if (!f[rt][j])
{
f[rt][j] = ++tot;
cnt[tot] = 0;
memset(f[tot], 0, sizeof(f[tot]));
}
rt = f[rt][j]; ++cnt[rt];
}
}
if (s[0] == 's')
{
int rt = 1;
for (int i = 0, j; x[i]; i++)
{
j = x[i] - 'a';
if (!(rt = f[rt][j]))
{
printf("No\n"); rt = 0; break;
}
}
if (rt) printf("Yes\n");
}
if (s[0] == 'd')
{
int rt = 1;
for (int i = 0, j; x[i]; i++)
{
j = x[i] - 'a';
if (!f[rt][j]) { rt = 0; break; }
else rt = f[rt][j];
}
if (!rt) continue;
int tr = 1;
for (int i = 0, j; x[i]; i++)
{
j = x[i] - 'a';
if (!f[tr][j]) break;
else
{
int k = f[tr][j];
cnt[k] -= cnt[rt];
if (!cnt[k]) k = f[tr][j] = 0;
tr = k;
}
}
}
}
}
return 0;
}