正文

uvaphonelist（字典树）（查询是否有前缀或自身是其他的前缀）

贱人方  贱人方  2022-08-22  489

关键词：

Phone List

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 16341		Accepted: 5228

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let‘s say the phone catalogue listed these numbers:

Emergency 911
Alice 97 625 999
Bob 91 12 54 26

In this case, it‘s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob‘s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input

Sample Output

NO
YES

Source

Nordic 2007

【分析】字典树

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <time.h>
#include <string>
#include <map>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define lson(x) ((x<<1))
#define rson(x) ((x<<1)+1)
using namespace std;
typedef long long ll;
const int N=10;
const int M=1e6+10;
typedef struct TrieNode {
    int endflag;
    struct TrieNode *next[N];
} TrieNode;

TrieNode Memory[M];
int allocp=0;
bool flag;

void InitTrieRoot(TrieNode **pRoot) {
    *pRoot=NULL;
}

TrieNode *CreateTrieNode() {
    int i;
    TrieNode *p;

    p=&Memory[allocp++];
    p->endflag=0;
    for(i=0; i<N; i++) {
        p->next[i]=NULL;
    }
    return p;
}

void InsertTrie(TrieNode **pRoot,char *s) {
    int i,k;
    TrieNode *p;

    if(!(p=*pRoot))
        p=*pRoot=CreateTrieNode();
    i=0;
    while(s[i]) {
        k=s[i++]-‘0‘;
        if(p->next[k]) {
            if(p->next[k]->endflag==1||s[i]==‘‘) {
                flag=false;
                return;
            }
        } else p->next[k]=CreateTrieNode();
        p=p->next[k];
    }
    p->endflag=1;
}

int main() {
    char str[50];
    TrieNode *Root=NULL;
    int T;
    scanf("%d",&T);
    int n;
    while(T--) {
        flag=true;
        allocp=0;
        scanf("%d",&n);
        InitTrieRoot(&Root);
        for(int i=0; i<n; i++) {
            //gets(str);//用这个会超时
            scanf("%s",&str);
            if(flag) InsertTrie(&Root,str);
        }
        if(flag) printf("YES
");
        else printf("NO
");
    }


    return 0;
}

字典树trie树

...出现的次数例如：cat，cash，app，apple，aply，ok建一颗字典树这里有两种编号：1.相对整棵树而言（根据单词insert顺序dfs序）2.相查看详情

hdu5687problemc(字典树前缀增删查)

题意: 度熊手上有一本神奇的字典，你可以在它里面做如下三个操作：1、insert:往神奇字典中插入一个单词2、delete:在神奇字典中删除所有前缀等于给定字符串的单词3、search:查询是否在神奇字典中有一个字符串的前缀等于给... 查看详情

10-4字典树的前缀查询

前缀查询:查询字典树中是否存在以指定字符串为前缀的单词！mportjava.util.TreeMap;publicclassTrieprivateclassNodepublicbooleanisWord;publicTreeMap<Character,Node>next;publicNode(booleanisWord)this.isWord=isWord;next=newTreeMap<>();publicNode()this(false);privateNod... 查看详情

傻傻分不清吗？——trietree，字典树、前缀树概述

参考技术ATrie树，又叫字典树、前缀树（PrefixTree）、单词查找树或键树，是一种多叉树结构。上图是一棵Trie树，表示了关键字集合“a”,“to”,“tea”,“ted”,“ten”,“i”,“in”,“inn”。从上图可以归纳出Trie树的基本性... 查看详情

字典树(前缀树)--trie

参考技术A是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最... 查看详情

数据结构---[实现字典树[前缀树](trie)](代码片段)

文章目录1.字典树添加单词添加方法改进2.判断是否存在指定单词,判断是否存在指定前缀的单词;3.判断是否存在指定单词(这时会将单词中的.号视为任意字母)Trie(前缀树或者字典树),主要针对于字符串的检索问题;值不是直接保存... 查看详情

字典树原理与实现(代码片段)

文章目录字典树一、字典树节点二、字典树的插入三、字典树的查询四、算法练习[LeetCode2416.字符串的前缀分数和](https://leetcode.cn/problems/sum-of-prefix-scores-of-strings/)字典树字典树(trie)，又称前缀树，或单词查找树，是一... 查看详情

字典树原理与实现(代码片段)

带前缀修改的字典树(代码片段)

在一个Minecraft村庄中，村长有这一本小写字母构成的名册（字符串的表），每个名字旁边都记录着这位村民的声望值，而且有的村民还和别人同名。随着时间的推移，因为没有村民死亡，这个名册变得十分大。现在需要您来帮忙... 查看详情

hdu杭电1671/poj3630字典树

...是否有前缀相同的串如果存在输出NO否则输出YES思路：用字典树解决标记字典树总串的结尾查找出一个串内部是否有被标记的节点如果有那么说明存在前缀相同的串在插入字典树的时候判断是否存在AC代码： 1#include"iostream"2#in... 查看详情

实现前缀树(代码片段)

...实现Trie(前缀树)208.实现Trie树Trie树（又叫「前缀树」或「字典树」）是一种用于快速查询「某个字符串/字符前缀」是否存在的数据结构。其核心是使用「边」来代表有无字符，使用「点」来记录是否为「单词结尾」以及「其后... 查看详情

前缀树(字典树/trie)-----java实现(代码片段)

...1.题目描述2.问题分析3.代码实现一.前缀树1.什么是前缀树字典树（Trie树）是一种树形数据结构，常用于字符串的存储和查找。字典树的核心思想是利用字符串之间的公共前缀来节省存储空间和提高查询效率。它是一... 查看详情

字典树(trie树)(代码片段)

字典树主要是为了解决前缀匹配问题，比如下图的搜索输入前缀后匹配比如有6个字符串how，hi，her，hello，so，see，如果现在输入字符判断是否要前缀匹配指定字符串，必须一个字符串比较，如... 查看详情

字典树(trie树)(代码片段)

uva11362-phonelist

...否有一些号码是其它的前缀（或相等）。分析：字符串。字典树。利用字典树储存查询就可以，注意两种情况处理： 1.先短后长（前缀在前）；2.先长后短（前缀在后）。说明：第580题了，目标600╮(╯... 查看详情

#前缀统计~[字典树](代码片段)

前缀统计~[字典树]传送门题意给出N个字符串，进行M次询问，每次给出一个字符串，询问N个字符串中有多少个是它的前缀。思路字典树Trie入门题。字典树最典型的应用就是用来存储字符串。其中每个节点下有26个子节点（对应26... 查看详情

简单的字典树（前缀树）

写这个树，主要是为了完成这道题目。http://hihocoder.com/problemset/problem/1014代码如下，注释有比较详细的解释1#include<iostream>2#include<string>3#include<typeinfo>4#include<vector>5usingnamespacestd;67/****** 查看详情