程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1251 統計難題 (前綴樹)

hdu 1251 統計難題 (前綴樹)

編輯：C++入門知識

hdu 1251 統計難題 (前綴樹)

題意是：

Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).

思路很簡單，前綴數組入門題，對於每個結點，用val數組記錄當前字符串為前綴的字符串數量，之後就是插入，查詢操作了

代碼如下：

#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include  
#include 
#include
#include 
#include
using namespace std;  
#define LL long long  
const int maxnode = 1000000 ;
const int sigma_size = 26; 

struct Trie {
	int ch[maxnode][sigma_size];
	int val[maxnode];
	int sz;
	Trie() { sz = 1; memset(ch[0], 0, sizeof(ch[0]));};
	int idx(char c) {return c - 'a';}
	
	void insert(char *s) {
		int u = 0, n = strlen(s);
		for(int i = 0; i < n; i++) {
			int c = idx(s[i]);
			if(!ch[u][c]) {
				memset(ch[sz], 0, sizeof(ch[sz]));
				val[sz] = 1;
				ch[u][c] = sz++;
			}
			else val[ch[u][c]]++;
			u = ch[u][c];
		}
	}
	
	int find(char *s) {
		int u = 0, n = strlen(s);
		for(int i = 0; i < n; i++) {
			int c = idx(s[i]);
			if(!ch[u][c]) return 0;
			else u = ch[u][c];
		}
		return val[u];	
	}
};
Trie trie; 

int main() {
		char dic[11], qry[11];
		//freopen("input.txt", "r", stdin);	
		while(gets(dic) && strcmp(dic, "") != 0) {
		//	printf("%s\n", dic);
			trie.insert(dic);
		}
		while(gets(qry)) printf("%d\n", trie.find(qry));
		return 0;
}