SDUT OJ 2892——字典树

本文主要是介绍SDUT OJ 2892——字典树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

输入

输出

示例输入

5
aba
abb
w
aba
z

示例输出

2

60ms过10^6的数据，这个必然是一个数据结构题，本题用字典树，以前学的时候还会写，但是后来一直没用到它，就渐渐的淡忘了，没想到今天见了，居然栽到这上面了...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>struct node
{int flag;struct node *next[26];
}*head;char s[6];
int mx=-1;void creat()
{int l,i,j,ls;struct node *p,*q;p=(struct node *)malloc(sizeof(struct node));p=head;l=strlen(s);for(i=0;i<l;i++){ls=s[i]-'a';if(p->next[ls]==NULL){q=(struct node *)malloc(sizeof(struct node));for(j=0;j<26;j++){q->next[j]=NULL;}q->flag=0;p->next[ls]=q;}p=p->next[ls];}p->flag++;if(mx<p->flag)mx=p->flag;
}int main()
{int i,n;head=(struct node *)malloc(sizeof(struct node));for(i=0;i<26;i++){head->next[i]=NULL;}head->flag=0;scanf("%d%*c",&n);for(i=0;i<n;i++){scanf("%s",s);creat();}printf("%d\n",mx);return 0;
}

这篇关于SDUT OJ 2892——字典树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！