基本上找到一个标准前缀的问题是，只需要insert和search它功能。

这里的主要变化是我n该记录方法，这里n国旗代表的不是叶节点，但是话的标志这条道路后的数字。

然后找到需要找到一个词的前缀，假如未发现，返回0，这个前缀单词为前缀，假设找到，直接返回n就是答案了。由于有n个单词经过了这条路径。

查找效率是常数。

使用静态分配空间的办法。

#include <stdio.h>

#include <string.h>

const int MAX_N = 500000;

const int ARR_SIZE = 26;

const int MAX_WORD = 11;

struct Node

{

	int n;

	Node *arr[ARR_SIZE];

};

Node pool[MAX_N];

int poolId;

void clearNode(Node *p)

{

	p->n = 0;

	for (int i = 0; i < ARR_SIZE; i++)

	{

		p->arr[i] = NULL;

	}

}

void insert(Node *trie, char w[])

{

	int len = strlen(w);

	for (int i = 0; i < len; i++)

	{

		int j = w[i] - 'a';

		if (trie->arr[j] == NULL)

		{

			trie->arr[j] = &pool[poolId++];

			clearNode(trie->arr[j]);

		}

		trie = trie->arr[j];

		trie->n++;	//改动成能够高速查找前缀

	}

}

int searchPre(Node *trie, char w[])

{

	int len = strlen(w);

	for (int i = 0; i < len; i++)

	{

		int j = w[i] - 'a';

		if (!trie->arr[j]) return 0;

		trie = trie->arr[j];

	}

	return trie->n;

}

int main()

{

	Node *trie = &pool[0];

	clearNode(trie);

	poolId = 1;

	char word[MAX_WORD];

	while (gets(word) && word[0] != '\0')

	{

		insert(trie, word);

	}

	while (gets(word))

	{

		printf("%d\n", searchPre(trie, word));

	}

	return 0;

}