首页 > 代码库 > 统计单词出现的最多次数（Trie树）

统计单词出现的最多次数（Trie树）

2024-07-18 21:29:00   221人阅读

A

Time Limit: 60ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

给出n(1<= n && n <= 2*10^6)个字符串,每个字符串只包含小写英文字母，且最多有五个。问这n个字符串中出现次数最多的有多少个。

输入

单组输入。第一行输入一个数字n，接下来n行，每行包含一个字符串。

输出

输出一个数字代表答案。

示例输入

5
aba
abb
w
aba
z

示例输出

2


参考自算法竞赛训练指南。话说啸爷出题就爱卡STL。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=900000;
int ch[maxn][26];//ch[i][j]保存节点i的那个编号为j的子节点
int val[maxn];//记录每个单词上面的附加信息
int sz,Max=-1;//sz为节点总数
void insert(char *s)//插入
{
	int u=0,len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int c=s[i]-'a';
		if(!ch[u][c])
		{
			memset(ch[sz],0,sizeof(ch[sz]));
			ch[u][c]=sz++;
		}
		u=ch[u][c];
	}
	val[u]++;
	if(Max<val[u])
		Max=val[u];
}
int main()
{
    char s[7];int n;
    scanf("%d",&n);getchar();
    sz=1;
    memset(ch[0],0,sizeof(ch[0]));//最开始只有一个根节点
    memset(val,0,sizeof(val));
    while(n--)
	{
		scanf("%s",s);
		insert(s);
	}
	printf("%d\n",Max);
	return 0;
}



联系
我们