| ||||||||||
| 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