HDU 1251 - 통계 난제 (사전 트 리 - 통계 접두사 문자열)

통계 적 난제
Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others) Total Submission(s): 29895    Accepted Submission(s): 11668
Problem Description
Ignatius 는 최근 어 려 운 문제 에 부 딪 혔 습 니 다. 선생님 께 서 는 그 에 게 많은 단어 (소문 자로 만 구성 되 어 있 고 중복 되 는 단어 가 나 오지 않 습 니 다) 를 주 셨 습 니 다. 지금 선생님 께 서 는 어떤 문자열 을 접두사 로 하 는 단어 수 (단어 자체 도 자신의 접두사) 를 집계 하 라 고 하 셨 습 니 다.
 
Input
데 이 터 를 입력 하 는 첫 번 째 부분 은 단어 표 입 니 다. 줄 마다 단어 가 있 고 단어의 길 이 는 10 을 넘 지 않 습 니 다. 선생님 이 Ignatius 에 게 통계 한 단 어 를 대표 합 니 다. 빈 줄 은 단어 표 의 끝 을 대표 합 니 다. 두 번 째 부분 은 일련의 질문 입 니 다. 줄 마다 질문 이 있 고 모든 질문 은 하나의 문자열 입 니 다.
메모: 이 문 제 는 파일 이 끝 날 때 까지 테스트 데이터 만 있 습 니 다.
 
Output
질문 마다 이 문자열 을 접두사 로 하 는 단어의 수 를 알려 줍 니 다.
 
Sample Input

   
   
   
   

    
    
    
    banana
band
bee
absolute
acm

ba
b
band
abc
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    2
3
1
0
   
   
   
   

 
Author
Ignatius.L
템 플 릿 을 씌 울 수 있 는 사전 트 리 누 드 문제 입 니 다. 단어 표 의 끝 을 나타 내 는 빈 줄 의 입력 끝 판단 에 주의 하 십시오.

/* 
* Copyright (c) 2016,                
* All rights reserved. 
*     ：tree.cpp 
*       ：    
*     ：2016 5 4  
*      ：v1.0 
*/  
#include <cstdio>
#include <iostream>
using namespace std;
struct Node
{
    int num,next[27];//num     
};

Node a[1000005];
int n,e;

void Insert(char str[])
{
    int i,p=1;
    for (i=0; str[i]; i++)
    {
        if (a[p].next[str[i]-'a']==0)//           
        {
            a[p].next[str[i]-'a']=++e;
            a[e].num=0;
        }
        p=a[p].next[str[i]-'a'];
        a[p].num++;
    }
}

int Search(char str[])//    
{
    int i,p=1;
    for (i=0; str[i]; i++)
    {
        if (a[p].next[str[i]-'a']) p=a[p].next[str[i]-'a'];//         
        else return 0;//      0
    }
    return a[p].num;
}

int main ()
{
    char str[35];
    n=0;
    e=1;
    while(gets(str),*str)//    &&str[0]
        Insert (str),n++;
    while(gets(str))
        cout<<Search(str)<<endl;
    return 0;
}

하나의 트 리 가 있 으 면 메모리 제한 을 초과 하기 쉽 습 니 다. 예 를 들 어 다음 과 같 습 니 다.

#include <stdio.h>
#include <iostream>
using namespace std;
#define MAXN 26
typedef struct TrieNode
{
    int nCount;  //           
    struct TrieNode *next[MAXN]; //        
} TrieNode;
TrieNode Memory[1000000]; //      ， malloc     
int allocp = 0;

TrieNode * createTrieNode()
{//       。nCount   1， next  null
    TrieNode * tmp = &Memory[allocp++];
    tmp->nCount = 1;
    for (int i = 0; i < MAXN; i++)
        tmp->next[i] = NULL;
    return tmp;
}

void insertTrie(TrieNode * * pRoot, char * str)
{
    TrieNode * tmp = *pRoot;
    int i = 0, k;
    //         
    while (str[i])//       
    {
        k = str[i] - 'a'; //           
        if (tmp->next[k])//           
            tmp->next[k]->nCount++;//    ++
        else//            
            tmp->next[k] = createTrieNode();//       
        tmp = tmp->next[k];//            
        i++; //       
    }

}

int searchTrie(TrieNode * root, char * str)
{
    if (root == NULL)
        return 0;
    TrieNode * tmp = root;
    int i = 0, k;
    while (str[i])
    {
        k = str[i] - 'a';
        if (tmp->next[k]) tmp=tmp->next[k];
        else return 0;
        i++;
    }
    return tmp->nCount; //              nCount
}

int main()
{
    char s[35];
    TrieNode *Root = createTrieNode();
    while (gets(s) && s[0])
    {
        insertTrie(&Root, s);
    }
    while (gets(s)) //        
    {
        printf("%d
", searchTrie(Root, s));
    }
    return 0;
}