Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
HDU1671能过,,,poj这就过不了了。。。。#include<cstdio> #include<cstring> int N; struct Node { char c; int fre, isend; //fre是出现频率,isend为是否是最后一个号码,只要最后一个号码的频率>1,就出现重复的 struct Node *son, *bro; //儿子和兄弟结点 Node() { son = bro = NULL; isend = fre = 0; c = '\0'; } }*Tire; bool Create(Node* &root) { int M; root = new Node; scanf("%d", &M); getchar(); char s[11]; bool flag = false; for (int i = 0; i<M; i++) { scanf("%s", s); if (flag)continue; //已经找到重复的,后面的就不用再判断 Node* tmp = root; int l = strlen(s); for (int j = 0; j<l; j++) { if(flag)break; Node* p = tmp->son; if (p == NULL) { p = new Node; p->c = s[j]; tmp->son = p; } else { Node* pre = p; while (p != NULL&&p->c != s[j]) { pre = p; p = p->bro; } if (p == NULL) { p = new Node; p->c = s[j]; pre->bro = p; } } tmp = p; p->fre++; if (j == l - 1)tmp->isend = 1; //先判断重复的 if (tmp->isend&&tmp->fre>1) { flag = true; //有重复的 } } } return flag; } void Del(Node* &root) { if (root == NULL)return; Del(root->son); Del(root->bro); root->fre = root->isend = 0; delete root; root->son = root->bro = NULL; } int main() { scanf("%d", &N); while (N--) { if (Create(Tire))puts("NO"); else puts("YES"); // Del(Tire); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator