HDU 1251 统计难题

Solution:

Trie。插入字符串时，将前缀链上的所有结点的点权加一，代表该前缀出现次数。查询时直接返回出现次数即可。注意输入格式。

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=11;
const int M=5e5+10;
char s[N];
int tr[M][26];
int endpos[M];
struct trie
{
	int tot;//点数
	int rt;//根
	void init(){
		tot=0;
		rt=0;
	}
	void insert1(char s[],int lens){
		int pos=rt;
		for(int i=0;i<lens;++i){
			int v=s[i]-'a';
			if(!tr[pos][v])tr[pos][v]=++tot;
			pos=tr[pos][v];
			endpos[pos]++;
		}
		
	}
	int query(char s[],int lens){
		int pos=rt;
		for(int i=0;i<lens;++i){
			int v=s[i]-'a';
			if(!tr[pos][v])return 0;
			pos=tr[pos][v];
		}
		return endpos[pos];
	}
};
int main(){
	trie T;
	T.init();
	while(cin.getline(s,N)){
		int len=strlen(s);
		if(len==0)break;
		T.insert1(s,len);
	}
	while(cin.getline(s,N)){
		int len=strlen(s);
		printf("%d\n", T.query(s,len));
	}
	return 0;
}