题意:给你一系列互不相同的电话号码,若存在某个号码是其他某个号码的前缀,则输出不相容(NO), 否则输出相容(YES)。
#include <iostream> using namespace std; const int kind = 10;//代表字符种类,共10个,1,2,3,4,5,6,7,8,9,0. int cnt; //统计已经被占用的节点的g struct Treenode { bool flag;/*标记是否为电话号码的最后一个数字,若是flag=1*/ Treenode *next[kind]; } node[100000]; void Insert ( Treenode * &root, char *phnum ) { Treenode *location = root; if ( location == NULL ) { location = &node[cnt++]; root = location; } int id, i = 0, len = strlen(phnum); while ( phnum[i] ) { id = phnum[i] - '0'; if ( location->next[id] == NULL ) location->next[id] = &node[cnt++]; if ( i == len-1 ) /*电话号码的最后一个数字*/ location->next[id]->flag = true; ++i; location = location->next[id]; } } bool Search ( Treenode *root, char *phnum ) /*检测到不相容就返回true,否则返回false,不相容指的是某个已插入的号码是phnum的前缀,或者phnum是某个已插入号码的前缀*/ { Treenode *location = root; if ( location == NULL ) return false; int id, i = 0; while ( phnum[i] ) { id = phnum[i] - '0'; if ( location->next[id] == NULL ) return false; if ( location->next[id]->flag == true ) /*假设123已经插入,在检测12345时,发现3已经是某个号码的最后一个数字,则说明该号码是12345的前缀,找到不相容*/ return true; ++i; location = location->next[id]; } return true; } int main() { int t, n, find; char phnum[10]; Treenode *root; scanf("%d",&t); while ( t-- ) { cnt = find = 0; /*find标志是否检测到不相容,开始时肯定是相容的,则find=0*/ root = NULL; memset(node,NULL,sizeof(node)); scanf("%d",&n); while ( n-- ) { scanf("%s",phnum); if ( !find ) find = Search ( root, phnum ); if ( !find ) Insert( root, phnum ); } if ( find ) printf("NO\n"); else printf("YES\n"); } return 0; }