admin管理员组

文章数量:1130349

题意：
     给你一些字符串，然后问你他们中有没有一个串是另一个串的前缀。

思路：
      字典树水题，（这种水题如果数据不大（这个题目不知道大不大，题目没说估计不大），hash下也行，把每个串拆成len个串，然后map容器记录下就行了，不想存也
行，最后迭代一下也能出来），回来说字典树，就是最简单的前缀判断应用，我写的结构体里面有3个量，next[]， v(出现次数) ,mk （是不是某个字符串的最后一位），
在查找的时候如果我们碰到了已经mk的，那么就直接发现前缀了，某个字符串是当前串的前缀，还有一种情况就是没有发现mk但是当前串的最后一位出现的次数大于0，也算

是发现前缀，当前串为某个字符串的前缀。ok就这些。  


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Tree
{
    Tree *next[2];
    int v ,mk;
}Tree;

Tree root;

void Buid_Tree(char *str)
{
    int len = strlen(str);
    Tree *p = &root ,*q;
    for(int i = 0 ;i < len ;i ++)
    {
       int id = str[i] - '0';
       if(p -> next[id] == NULL)
       {
           q = (Tree *)malloc(sizeof(root));
           q -> v = 1;
           q -> mk = 0;
           for(int j = 0 ;j < 2 ;j ++)
           q -> next[j] = NULL;
           p -> next[id] = q;
           p = p -> next[id];
        }
        else
        {
            p = p -> next[id];
            p -> v ++;
        }
      }
      p -> mk = 1;
}

int Find(char *str)
{
    int len = strlen(str);
    Tree *p = &root;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - '0';
        p = p -> next[id];
        if(p == NULL) return 0;
        if(p -> mk == 1) return 2;
       
    }
    return p -> v;
}


int main ()
{
    char str[10000];
    int cas = 1;
    while(~scanf("%s" ,str))
    {
       if(!strcmp(str ,"9"))
       {
          printf("Set %d is immediately decodable\n" ,cas ++);
          continue;
       }
       root.next[0] = root.next[1] = NULL;
       Buid_Tree(str);
       int mk = 0;
       while(scanf("%s" ,str) && strcmp(str ,"9"))
       {
          if(Find(str) > 0) mk = 1;
          Buid_Tree(str);
       }
       if(!mk) printf("Set %d is immediately decodable\n" ,cas ++);
       else printf("Set %d is not immediately decodable\n" ,cas ++);
     }
     return 0;
}




题意：
     给你一些字符串，然后问你他们中有没有一个串是另一个串的前缀。

思路：
      字典树水题，（这种水题如果数据不大（这个题目不知道大不大，题目没说估计不大），hash下也行，把每个串拆成len个串，然后map容器记录下就行了，不想存也
行，最后迭代一下也能出来），回来说字典树，就是最简单的前缀判断应用，我写的结构体里面有3个量，next[]， v(出现次数) ,mk （是不是某个字符串的最后一位），
在查找的时候如果我们碰到了已经mk的，那么就直接发现前缀了，某个字符串是当前串的前缀，还有一种情况就是没有发现mk但是当前串的最后一位出现的次数大于0，也算

是发现前缀，当前串为某个字符串的前缀。ok就这些。  


#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct Tree
{
    Tree *next[2];
    int v ,mk;
}Tree;

Tree root;

void Buid_Tree(char *str)
{
    int len = strlen(str);
    Tree *p = &root ,*q;
    for(int i = 0 ;i < len ;i ++)
    {
       int id = str[i] - '0';
       if(p -> next[id] == NULL)
       {
           q = (Tree *)malloc(sizeof(root));
           q -> v = 1;
           q -> mk = 0;
           for(int j = 0 ;j < 2 ;j ++)
           q -> next[j] = NULL;
           p -> next[id] = q;
           p = p -> next[id];
        }
        else
        {
            p = p -> next[id];
            p -> v ++;
        }
      }
      p -> mk = 1;
}

int Find(char *str)
{
    int len = strlen(str);
    Tree *p = &root;
    for(int i = 0 ;i < len ;i ++)
    {
        int id = str[i] - '0';
        p = p -> next[id];
        if(p == NULL) return 0;
        if(p -> mk == 1) return 2;
       
    }
    return p -> v;
}


int main ()
{
    char str[10000];
    int cas = 1;
    while(~scanf("%s" ,str))
    {
       if(!strcmp(str ,"9"))
       {
          printf("Set %d is immediately decodable\n" ,cas ++);
          continue;
       }
       root.next[0] = root.next[1] = NULL;
       Buid_Tree(str);
       int mk = 0;
       while(scanf("%s" ,str) && strcmp(str ,"9"))
       {
          if(Find(str) > 0) mk = 1;
          Buid_Tree(str);
       }
       if(!mk) printf("Set %d is immediately decodable\n" ,cas ++);
       else printf("Set %d is not immediately decodable\n" ,cas ++);
     }
     return 0;
}




本文标签： 字典树水题

版权声明：本文标题：hdu1305 字典树水题 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/jiaocheng/1754583185a2704153.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。