통계 난제 HDU - 1251 (사전 트 리)

4365 단어 데이터 구조트 리 트 리
Ignatius 는 최근 에 어 려 운 문제 에 부 딪 혔 습 니 다. 선생님 께 서 는 그 에 게 많은 단어 (소문 자로 만 구성 되 어 중복 되 는 단어 가 나 오지 않 습 니 다) 를 주 셨 습 니 다. 지금 선생님 께 서 는 어떤 문자열 을 접두사 로 하 는 단어 수 (단어 자체 도 자신의 접두사 입 니 다) 를 집계 하 라 고 하 셨 습 니 다. Input 입력 데이터 의 첫 번 째 부분 은 단어 표 입 니 다. 줄 마다 단어, 단어의 길이 가 10 을 넘 지 않 습 니 다.그들 은 선생님 이 Ignatius 에 게 통계 한 단 어 를 대표 합 니 다. 빈 줄 은 단어 표 의 끝 을 대표 합 니 다. 두 번 째 부분 은 일련의 질문 입 니 다. 줄 마다 질문 이 있 고 모든 질문 은 문자열 입 니 다.
메모: 이 문 제 는 파일 이 끝 날 때 까지 테스트 데이터 만 있 습 니 다. Output 은 모든 질문 에 이 문자열 을 접두사 로 하 는 단어의 수 를 보 여 줍 니 다. Sample Input banana band bee absolute acm
ba b band abc Sample Output 2, 3, 10 사전 트 리 의 입문 문제 입 니 다. 이 문 제 는 G + + 로 초 메모리, C + + 는 A 가 가능 합 니 다.
#include
#include
#include
#include
#include
using namespace std;
struct node
{
    int countt;
    node *charr[26];
} *root;
void init()
{
    root=new node;
    for(int i=0;i<26;i++)
        root->charr[i]=NULL;
}
void insertt(char* str)//  
{
    int len,cur;
    node *head=root;
    len=strlen(str);
    for(int i=0;iint)(str[i]-'a');
        if(head->charr[cur]==NULL)
        {
            head->charr[cur]=new node;
            head=head->charr[cur];
            head->countt=1;
            for(int j=0;j<26;j++)
            {
                head->charr[j]=NULL;
            }
        }
        else
        {
            head=head->charr[cur];
            head->countt++;
        }
    }
}
int searchh(char* str)//  
{
    int len,cur;
    node *head=root;
    len=strlen(str);
    for(int i=0;iint)(str[i]-'a');
        if(head->charr[cur]==NULL)
            return 0;
        else
            head=head->charr[cur];
    }
    return head->countt;
}
int main()
{
    char str[15],que[15];
    int temp,query;
    init();
    while(gets(str)&&strcmp(str,"")!=0)
        insertt(str);
    while(scanf("%s",que)!=-1)
    {
        printf("%d
",searchh(que));
    }
    return 0;
}
Spring+Gradle 종속 관리 학습 노트
나무 - 2 - 3 - 4 나무, B 나무 (B + 나무, B - 나무)

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage