Trie字元串統計數組實作

字典樹 (Trie)

字典樹，英文名 trie。顧名思義，就是一個像字典一樣的樹。

基本性質：

1.根節點不包含字元，除根節點外的每一個子節點都包含一個字元

2.從根節點到某一節點。路徑上經過的字元連接配接起來，就是該節點對應的字元串

3.每個節點的所有子節點包含的字元都不相同

用數組來存取樹方法實作：

首先準備一個二維數組

son[N][M]

和一個結點編号器

idx

。

思想：

1.

son

中的

N

表示父結點的編号，

M

表示該點字元元素，整個

son[N][M]

表示父結點為

N

，字元元素為

M

的結點（實際就是通過父節點來通路孩子結點）。

2

idx

的作用是給結點編号，使每一個結點獨一無二(實際為了給父節點命個名來區分父節點)。

例：

輸入三個字元串形成的樹。

a b c

a b

b d

代碼實作：

void insert()
{
	int p = 0; //根節點
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a'; // 孩子結點對應的元素,字元不能當下标
 		if (!son[p][u]) son[p][u] = ++idx; // 給孩子結點編号，實際是為了區分結點
		p = son[p][u]; // 孩子結點做父結點
	}
}
           

圖像：

每個結點前面的數代表結點編号。

通過結點編号（父結點）可以通路，該結點的孩子結點，即

son[N][M]

中的

N

。

但隻知道結點編号還不行，還需要知道孩子元素，來确定通路哪個孩子結點。

例：編号為

1

的結點的孩子對應的孩子元素為

b

，

d

，即孩子元素為

b

對應的結點為

son[i][b]

（這裡不能真的用b）該結點的值為該結點的編号。

例題：

維護一個字元串集合，支援兩種操作：

I x 向集合中插入一個字元串 x；

Q x 詢問一個字元串在集合中出現了多少次。

共有 N 個操作，字元串僅包含小寫英文字母。

實作代碼：

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

char c[N];
int son[N][26]; // 孩子結點
int cnt[N]; // 統計字元串
int idx; // 結點編号器


void insert()
{
	int p = 0;
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a'; // 孩子結點對應的元素
 		if (!son[p][u]) son[p][u] = ++idx; // 給孩子結點編号，使孩子節點獨一無二
		p = son[p][u]; // 孩子結點做根結點
	}
	// 從根節點到此孩子結點的字元串出現的次數，
	// 因為每個子樹都是獨一無二的，是以p對應的子樹也是獨一無二的
	// 是以隻要保證葉子結點加1，就可以表示這個子樹加1。
	cnt[p]++; 
}

void query()
{
	int p = 0;
	for (int i = 0; c[i]; i++)
	{
		int u = c[i] - 'a';
		p = son[p][u];
	}
	cout << cnt[p] << endl;
}

int main()
{
	int n; cin >> n;
	while (n--)
	{
		char op[2];
		scanf("%s%s",op, c);
		if (op[0] == 'I') insert();
		else query();
	}
}