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

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;

}