返回首页 返回专题

【BZOJ1174】Toponyms 题解

纵眼望去，大水题，一棵Trie轻松搞定。可是少年，你知道“坑”这个字怎么念吗？

首先是没告诉你字符串总长，根据文件大小计算，应该有400万个字符，然而内存限制128MB，所以你还敢开一个ch[N][26]数组吗？

就算我给你1024MB，你也不能这样开，因为，没人告诉你字符串只包含英文字母……甚至还有空格……

于是你连scanf都不能使用了，只能使用BUG一大堆的gets语句

于是你需要判定你gets进来的是不是空串，或者是不是一个换行符

然后再回到上面那个ch数组的问题，你不得不使用链式前向星，以时间来换取空间

这本是一道大水题，可是为何遍地是坑……

#include<bits/stdc++.h>
using namespace std;

const int N=5000010;
int h[N],nxt[N],ch[N],to[N];
int tot=1,cnt[N],ans=0,etot=0;
char s[N];

void insert()
{
	int p=1,l=strlen(s);
	for(int i=0;i<l;i++)
	{
		int tmp,j=s[i];
		for(tmp=h[p];tmp;tmp=nxt[tmp])
			if(ch[tmp]==j) break;
		if(ch[tmp]!=j)
		{
			ch[++etot]=j;
			to[etot]=++tot;
			nxt[etot]=h[p];
			h[p]=etot;
			p=to[etot];
		}
		else p=to[tmp];
		cnt[p]++;
		ans=max(ans,cnt[p]*(i+1));
	}
}

int main()
{
	int n;scanf("%d",&n);
	while(gets(s))
	{
		if(strlen(s)==0) continue;
		if(s[0]=='\n') continue;
		insert();
	}
	cout<<ans<<endl;
	return 0;
}