Trie树

【题目链接】Trie树

&题意：

输入

输入的第一行为一个正整数n，表示词典的大小，其后n行，每一行一个单词（不保证是英文单词，也有可能是火星文单词哦），单词由不超过10个的小写英文字母组成，可能存在相同的单词，此时应将其视作不同的单词。接下来的一行为一个正整数m，表示小Hi询问的次数，其后m行，每一行一个字符串，该字符串由不超过10个的小写英文字母组成，表示小Hi的一个询问。

n, m<=100000，词典的字母表大小<=26.

输出

对于小Hi的每一个询问，输出一个整数Ans,表示词典中以小Hi给出的字符串为前缀的单词的个数。

&题解：

Trie蓝书模板

&代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

typedef long long ll;

const int maxNo= 1000000 +7,sSi=26;

struct Trie {

	int ch[maxNo][sSi],val[maxNo],sz;

	void init() {sz=1; memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val));}

	int idx(char c) {return c-'a';}

	void insert(char *s) {

		int u=0;

		for(int i=0; s[i]; i++) {

			int c=idx(s[i]);

			if(!ch[u][c]) {

				memset(ch[sz],0,sizeof(ch[sz]));

				ch[u][c]=sz++;

			}

			u=ch[u][c];

			val[u]++;

		}

	}

	int query(char *s) {

		int u=0;

		for(int i=0; s[i]; i++) {

			int c=idx(s[i]);

			if(!ch[u][c]) return 0;

			u=ch[u][c];

		}

		return val[u];

	}

} tr;

int n,m;

char s[20];

int main() {

	freopen("E:1.in","r",stdin);

	while(~scanf("%d",&n)) {

		tr.init();

		for(int i=0; i<n; i++) {

			scanf("%s",s);

			tr.insert(s);

		}

		scanf("%d",&m);

		// for(int i=0; i<5; i++) {

		// 	printf("%d ",tr.val[i]);

		// } puts("");

		for(int i=0; i<m; i++) {

			scanf("%s",s);

			// puts(s);

			printf("%d\n",tr.query(s));

		}

	}

	return 0;

}

巴特西

hiho #1014 : Trie树(模板)

Trie树

最新文章

热门文章