ACM: Gym 100935F A Poet Computer - 字典树
Time Limit:2000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u
Description
The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constructed a dictionary of words, They are interested only in the longest common suffix, That is, a suffix common to three or more words in the dictionary… A suffix is any substring that starts from some arbitrary position in the string and reaches the end of the string. As the ACM team was also preparing for the ACM-TCPC2015 contest, they figured that the contestants can help in solving this problem. Your task is to write a program that finds a longest common suffix in a dictionary of words. An entry in the dictionary is a word of English letters only. Small letters are the same as capital letters. You can assume that there is exactly one unique solution for every test case.
Input
The first line of the input contains an integer T, the number of test cases. Each test case starts with a line containing one integer K, then K lines follow, each containing one string “Si” that represents an entry in the dictionary. 0 < T ≤ 50 |Si| ≤ 100 0 < K ≤ 1000
Output
For each test case, print on the first line “Case c:” where ‘c’ is the test case number. On the second line you should print an integer denoting the length of the longest common suffix and another integer denoting how many words have the suffix appeared in.
Sample Input
2
4
cocochannel
chrisschannel
MBCchannel
controlpanel
5
superman
batman
ironman
chrissbrown
MyCrown
Case 1:
7 3
Case 2:
3 3
/*/
题意:找最长常见后缀; 单纯的字典树,找后缀数大于等于3,长度尽可能大的后缀。 AC代码:
/*/
#include"algorithm"
#include"iostream"
#include"cstring"
#include"cstdlib"
#include"cstdio"
#include"string"
#include"vector"
#include"queue"
#include"cmath"
using namespace std;
typedef long long LL ;
#define memset(x,y) memset(x,y,sizeof(x))
#define memcpy(x,y) memcpy(x,y,sizeof(x))
#define FK(x) cout<<"["<<x<<"]\n" struct Trie {
int v;
int len;
Trie *next[26];
} root; struct Ans {
int len,num;
} ans,t; void init() {
ans.len=ans.num=0;
t.len=t.num=0;
} void BuildTree(char *s) {
// FK("NO");
int len=strlen(s);
Trie *p=&root,*q;
for(int i=len-1; i>=0; i--) {
int num;
// if(!((s[i]<='Z'&&s[i]>='A')||(s[i]<='z'&&s[i]>='a')))continue;
if(s[i]<='z'&&s[i]>='a')num=s[i]-'a';
else num=s[i]-'A';
if(p->next[num]==NULL) {
q=(Trie *)malloc(sizeof(root));
q->v=1;
for(int j=0; j<26; j++) {
q->next[j]=NULL;
}
q->len=p->len+1;
p->next[num]=q;
p=p->next[num];
} else {
p=p->next[num];
p->v++; }
if(p->v >= 3&&p->len >= t.len) {
t.len=p->len;
t.num=p->v;
}
}
} void DeleteTrie(Trie *T,int k) {
if (T==NULL) return ;
for(int i=0; i<26; i++) {
if(T->next[i]!=NULL) {
DeleteTrie(T->next[i],k+1);
}
}
if(k==0) {
for(int i=0; i<26; i++) {
T->next[i]=NULL;
}
} else free(T);
return ;
} int main() {
int T,n;
char s[205];
scanf("%d",&T);
for(int qq=1; qq<=T; qq++) {
scanf("%d",&n);
init();
for(int i=0; i<n; i++) {
cin>>s;
BuildTree(s);
if(t.num>=3&&t.len>=ans.len) {
ans=t;
}
}
printf("Case %d:\n", qq);
printf("%d %d\n",ans.len,ans.num);
Trie *p=&root;
DeleteTrie(p,0);
}
return 0;
}
最新文章
- textField和textView限制输入条件
- Jmeter操作手册
- 10 位顶级 PHP 大师的开发原则
- 写给自己的Java程序员学习路线图
- ASP.NET 大文件上传的简单处理
- JavaWeb项目开发案例精粹-第2章投票系统-005实体层
- yarn环境的搭建
- 网络环境场景以及模拟工具netem
- hl7 java 解析
- 戏说HTML5(转)
- FORTH基础
- java反射机制--reflection
- python Ajax
- Spring之BeanFactory和FactoryBean接口的区别
- 【慕课网实战】Spark Streaming实时流处理项目实战笔记三之铭文升级版
- 学习排序算法(一):单文档方法 Pointwise
- centos 7安装jdk、tomcat
- linux中vim的常用方法
- 2018.08.22 hyc的xor/mex(线段树/01trie)
- rhel和centos7下更改网卡名称ens33为eth0