사전 트 리, 사전 트 리 코드

사전 트 리 개념:
사전 트 리 는 말 그대로 알파벳 등 문자열 을 처리 하 는 특수 한 데이터 구조 이다.말하자면 스물 여섯 갈래 나무 다.머리 지침 을 정의 하고 머리 지침 부터 시작 합 니 다.
사전 트 리 분석:
단어의 주파 수 를 통계 하 는 방식 에 대해 서도 hash 같은 방법 을 사용 할 수 있 지만 사전 트 리 를 사용 하 는 것 이 좋 습 니 다. 사전 트 리 는 접 두 사 를 통계 할 수 있 지만 hash 에 서 는 실현 할 수 없습니다.
극단 적 인 상황 에서 각 노드 아래 에 26 개의 자모 가 있 으 면 차지 하 는 공간 은 26 ^ n 이 고 그 중에서 n 은 단어의 평균 길 이 를 나타 낸다.그러나 단어 에 대해 많은 노드 가 나타 날 수 없고 일부 노드 는 고주파 로 나타난다. 예 를 들 어 단어의 접두사 pre 등 이다. 그러면 사전 트 리 로 빠 른 검색 과 삽입 을 할 수 있 고 단어의 주파수 와 접 두 사 를 통계 할 수 있어 매우 효율 적 이다.
두 가지 상용 동작 이 있 습 니 다. 1. 어떤 문자열 의 출현 횟수 를 조회 합 니 다.이 문자열 이 끝 날 때 까지 노드 마다 count 를 0 으로 설정 합 니 다. 끝 에 count + +. 이렇게 하면 이 문자열 의 출현 횟수 를 기록 합 니 다.2. 특정한 문자열 의 특정한 시퀀스 가 나타 나 는 횟수 를 조회 합 니 다.각 노드 의 count 가 0 으로 초기 화 되 었 습 니 다. 한 문 자 를 읽 으 면 count + + 입 니 다.이렇게 조회 할 때 이 노드 count 는 처음부터 이 노드 까지 특정한 서열 이 나타 나 는 횟수 를 기록 합 니 다.단 어 를 집계 할 수 있 는 접두사 같은 제목 입 니 다.

#include <string>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
#define MAX 26	//the total number of alphabet is 26, a...z

struct Dictree
{
	bool word;
	int count;
	struct Dictree *trie[MAX];	// the 26 child
} * a;

int init()		// init the chained list
{
	a = new Dictree;
	for(int i = 0; i < MAX; i++)
	{
		a->trie[i] = NULL;
		a->word = false;
	}

	return 0;
}

bool searchTrie(char *str)
{
	int len, res;
	Dictree *head = a;
	assert(head);
	len = strlen(str);

	for(int i = 0; i < len; i++)
	{
		res = (int)(str[i] - 'a');
		if(head->trie[res] == NULL)
			return false;
		head = head->trie[res];
	}

	if(head->word)
		return true;

	return false;
}

int insertTrie(char *str)
{
	int len, res;
	Dictree *head = a;
	len = strlen(str);

	for(int i = 0; i < len; i++)
	{
		res = int(str[i] - 'a');
		if(head->trie[res] == NULL)		//whether the node exist?
		{
			head->trie[res] = new Dictree;
			head = head->trie[res];
			head->count = 0;
			for(int j = 0; j < MAX; j++)
			{
				head->trie[j] = NULL;
				head->word = false;
			}
		}
		else
			head = head->trie[res];
	}
	head->count++;
	head->word = true;

	return head->count;
}

int main()
{
	char str[20];

	init();
	for(int i = 0; i < 10; i++)
	{
		scanf("%s", str);
		printf("%d
", insertTrie(str));
	}

	scanf("%s", str);
	printf("%s
", searchTrie(str) ? ("YES"):("NO"));

	return 0;
}

PS: 1 판 에 Dictree 에 bool word 판정 을 넣 지 않 았 습 니 다. 단 어 를 찾 는 것 이 정확 하지 않 습 니 다. 워드 판정 을 넣 으 면 현재 노드 word = = true 는 뿌리 노드 에서 이 노드 까지 하나의 단 어 를 표시 합 니 다. false 라면 이 노드 가 단어 중간 에 있 음 을 표시 합 니 다.