您现在的位置是:首页 > 正文

Hats’Worlds(字典树)

2024-02-01 05:30:16阅读 2

Hats’World

Problem Description:
A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary.
You are to find all the hat’s words in a dictionary.
Input:
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words.
Only one case.
Output:
Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input:
a
ahat
hat
hatword
hziee
word
Sample Output:
ahat
hatword
题目大意:
给定一组单词,让你找到一个单词,使得这个单词由这组单词中出现过的两个单词构成。
例:ahat由a和hat构成,而a和hat在这组单词中出现过。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=50010;
struct node
{
    int next[27];
    int b;
}tree[maxn];
int tot=1,sum,top,stack[maxn];
char s[maxn][27];
void build_tree(int l,char s[])
{
    int now=0;
    for(int i=0;i<l;i++)
    {
        int x=s[i]-96;
        if(tree[now].next[x])
        now=tree[now].next[x];
        else
        {
            tree[now].next[x]=++sum;
            now=sum;
        }
    }
    tree[now].b=true;
}
int can(int l,char s[])
{
    int i=0,now=0,top=0;
    for(int i=0;i<l;i++)
    {
        int x=s[i]-96;
        if(tree[now].next[x])
        now=tree[now].next[x];
        else return 0;
        if(tree[now].b&&s[i])
        stack[top++]=i+1;
    }
    while(top)
    {
        int now=0;
        bool flag=1;
        int x=stack[--top];
        while(s[x])
        {
            if(!tree[now].next[s[x]-96])
            {
                flag=0;
                break;
            }
            now=tree[now].next[s[x]-96];
            x++;
        }
        if(flag&&tree[now].b)
        return 1;
    }
    return 0;
}
int main()
{
    while(gets(s[tot])&&strlen(s[tot]))
    {
        int len=strlen(s[tot]);
        build_tree(len,s[tot]);
        tot++;
    }
    for(int i=1;i<=tot;i++)
    {
        int len=strlen(s[i]);
        if(can(len,s[i]))
        cout<<s[i]<<endl;
    }
    return 0;
}

网站文章

  • Centos 7.6安装Docker

    Centos 7.6安装Docker

    我是在腾讯云轻量服务器上安装的,参考的是docker的官网的教程,链接:Install Docker Engine on CentOS | Docker DocumentationInstructio...

    2024-02-01 05:30:08
  • 卷积计算,反卷积计算,特征图大小计算,空洞卷积计算

    卷积计算,反卷积计算,特征图大小计算,空洞卷积计算

    转自:https://www.jianshu.com/p/09ea4df7a788?utm_source=oschina-app 卷积计算过程(单/RGB多通道) 特征图大小计算公式 转置卷积(反卷积)计算过程 空洞卷积计算过程 卷积计算过程(单/RGB多通道) 假设输入层的大小为 5 x 5,局部感受野(或称卷积核)的大小为 3 x 3,那么输出层一个神经元所对应的计算过程(下文...

    2024-02-01 05:30:01
  • java stringutil 工具类_StringUtil字符串相关的工具类常用方法详解

    java stringutil 工具类_StringUtil字符串相关的工具类常用方法详解

    StringUtil字符串相关的工具类常用方法static int ChineseLength(java.lang.String str)获取一个字符串中中文字符的个数static int countSubStr(java.lang.String string, java.lang.String str)获取字符串str在String中出现的次数static int countSubStrR...

    2024-02-01 05:29:52
  • Java根据对象属性合并

    Java根据对象属性合并

    效果代码实现import java.util.ArrayList;import java.util.List;public class TestDemo { public static void...

    2024-02-01 05:29:23
  • URL最大长度问题

    这几天为解决一个BUG头疼了一段时间,BUG现象如下:一个选择人员的选择控件,当选择多个人时(50多个的时候),返回没有错误现象,而再一次打开的时候就报404错误。看到这个错误非常纳闷,无法下手,只能再一次看控件的代码,在详细看代码时,发现所有的参数都是经过URL传参的,赶紧百度一下URL参数的大小限制(从这个百度开始,我就进入一个误区:参数大小的限制)。结果发现网上都说URL参数的大小为

    2024-02-01 05:29:15
  • c语言是学电脑吗,c语言入门至精通这些天一直有人问我,c语言好学吗?我是个新手...

    c语言是学电脑吗,c语言入门至精通这些天一直有人问我,c语言好学吗?我是个新手...

    这些天一直有人问我,c语言好学吗?我是个新手,该如何学习?其实,这类问题困扰着很多新手。在如何学习之前,我们想简单的了解一下什么是C语言:C语言是一种计算机程序设计语言。它既有高级语言的特点,又具有汇...

    2024-02-01 05:29:04
  • 组件化开发之git使用

    组件化开发之git使用

    初始化本地代码仓库添加到暂缓区本地仓库状态查询 绿色就是添加到暂缓区的文件本地仓库提交日志提交到原创仓库 这里有个变化 之前是master 现在变成main 理由就是规避种族歧视风险打本地标签提交到远程仓库标签提交到指定的tag查看原创仓库提交的tag本地删除标签远程删除 标签...

    2024-02-01 05:28:35
  • 解决visual studio community 2022运行c++程序卡顿问题

    解决visual studio community 2022运行c++程序卡顿问题

    解决visual studio community 2022运行c++程序卡顿问题

    2024-02-01 05:28:27
  • 4路红外循迹模块使用教程

    4路红外循迹模块使用教程

    4路红外循迹模块使用教程文章目录4路红外循迹模块使用教程模块详细信息:模块接线模块使用相关代码模块详细信息:工作电压:DC 3.3V~5V工作电流:尽量选择1A以上电源供电工作温度:-10℃~+50℃...

    2024-02-01 05:28:21
  • 网络安全人才的发展情况是怎么样的呢?快上车,带你了解

    网络安全人才的发展情况是怎么样的呢?快上车,带你了解

    前言 根据报告执行的数据分析情况,今年因疫情影响及新基建的提出,导致网络安全人才的择业及网络安全从业人员的流动受到一些影响,目前网络安全人才培养方面存在以下几个主要特点: (1)在校网络安全人才中性别...

    2024-02-01 05:27:52