[poj] 2945 Find the Clones

原题

听说用map可以3s水过这个5s题……
就是个Trie树板子，很好写，但是用链前连边时，head数组没有开成结点数，然后RE刷了好久……

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 20010
using namespace std;
int head[100*N],n,l,now,t,ans,tm[N];
char s[50];
struct hhh
{
    char to;
    int next,cnt;
} edge[100*N];

void add(int u,char v)
{
    edge[t].cnt=0;
    edge[t].to=v;
    edge[t].next=head[u];
    head[u]=t++;
}

void insert()
{
    now=1;
    bool b;
    for (int i=1;i<=l;i++)
    {
	b=0;
	for (int j=head[now];j;j=edge[j].next)
	    if (edge[j].to==s[i])
	    {
		now=j;
		b=1;
		break;
	    }
	if (!b) add(now,s[i]),now=head[now];
    }
    edge[now].cnt++;
    tm[edge[now].cnt]++;
    tm[edge[now].cnt-1]--;
}

int main()
{
    while (~scanf("%d%d",&n,&l))
    {
	if (n==0 && l==0) break;
	t=1;
	for (int i=1;i<=n;i++) tm[i]=0;
	memset(head,0,sizeof(head));
	for (int i=1; i<=n; i++)
	{
	    scanf("%s",s+1);
	    insert();
	}
	for (int i=1;i<=n;i++)
	    printf("%d\n",tm[i]);
    }
    return 0;
}