2016「百度の星」-資格試合(Astar Round 1)Problem C(辞書ツリー)

Problem C  
 
 Time Limit: 2000/1000 MS (Java/Others)
 
 Memory Limit: 131072/131072 K (Java/Others)
Problem Description
度熊の手には不思議な辞書があります.その中で次の3つの操作をすることができます.

1、insert :             

2、delete:                       

3、search:                            

Input
ここにはテストデータのセットしかありません.1行目は正の整数N(1leq Nleq 100000)N(1≦N≦100000)を入力し、辞書に対するクマの操作回数を表し、次にNN行、各行は2つの文字列を含み、中間にスペースで区切られている.最初の文字列は、関連する操作(insert、delete、またはsearchを含む)を表します.2番目の文字列は、関連する操作後に指定された文字列を表し、2番目の文字列の長さは30を超えません.2番目の文字列は小文字のみで構成されます.
Output
各search操作について、度熊の辞書に所定の文字列が接頭辞である単語が存在する場合、Yesを出力し、そうでなければNoを出力する.
Sample Input

5
insert hello
insert hehe
search h
delete he
search hello

Sample Output

Yes
No

解題の考え方:普通の辞書ツリー(挿入、削除、クエリー機能付き)
1 insert:挿入操作、入力した文字列sを挿入する.
②search:クエリ操作で、文字列sを接頭辞とする文字列があるかどうかを尋ねる
③delete:削除操作、文字列sを接頭辞とするすべての文字列(接頭辞自体を含む)を削除
以前からディクショナリツリーテンプレートがありましたが、削除操作はありませんでしたので、裸で削除操作をタップすればAC
削除操作では、接頭辞文字列sの最後のアルファベットノードを初期化することで削除機能を達成していますが、前駆ノードの値を更新するのを初めて忘れてWAが発生しました.
理解しやすいように、テストデータをセットします.
INPUT
4
insert hello
search h
detele hell
search h
OUTPUT
Yes
No
タイトルリンク→HDU 5687 Problem C

/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 35;
const int M = 26;
const int inf = 100000000;
const int mod = 2009;
struct tree
{
    int a[M],t;
}s[1000005];
char ch[N];
int p;
void init(int x)
{
    s[x].t=0;
    memset(s[x].a,-1,sizeof(s[x].a));
}
void buildtree()
{
    int i,k=0;
    for(i=0;ch[i]!='\0';i++)
    {
        if(s[k].a[ch[i]-'a']==-1)
        {
            s[k].a[ch[i]-'a']=p;
            init(p++);
        }
        k=s[k].a[ch[i]-'a'];
        s[k].t++;
    }    
}
void query()
{
    int i,k=0;
    for(i=0;ch[i]!='\0';i++)
    {
        if(s[k].a[ch[i]-'a']==-1)
        {
            puts("No");
            return ;
        }
        k=s[k].a[ch[i]-'a'];
    }
    if(s[k].t)
        puts("Yes");
    else
        puts("No");
}
void deletetree()
{
    int i,k=0,z;
    for(i=0;ch[i]!='\0';i++)
    {
        if(s[k].a[ch[i]-'a']==-1)
            return ;
        k=s[k].a[ch[i]-'a'];
    }
    z=s[k].t;
    for(k=i=0;ch[i]!='\0';i++)
    {
        k=s[k].a[ch[i]-'a'];
        s[k].t-=z;
    }
    init(k);
}
char x[10];
int main()
{
    int n,m,i;
    while(~scanf("%d",&n))
    {
        p=0;init(p++);
        for(i=0;i<n;i++)
        {
            scanf("%s%s",x,ch);
            if(x[0]=='i')
                buildtree();
            else if(x[0]=='s')
                query();
            else
                deletetree();
        }
    }
    return 0;
}

菜鳥成長記