UVa409_Excuses, Excuses!(小白书字符串专题)[通俗易懂]

UVa409_Excuses, Excuses!(小白书字符串专题)

大家好,又见面了,我是全栈君。

解题报告

题意:

找包括单词最多的串。有多个按顺序输出

思路:

字典树爆。

#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;
int k,e,num[100],cnt;
struct node
{
    int v;
    node *next[26];
};
node *newnode()
{
    node *p=new node;
    p->v=0;
    int i;
    for(i=0;i<26;i++)
        p->next[i]=NULL;
    return p;
}
void addnode(node *root,char *str)
{
    int i,l=strlen(str);
    node *p=root;
    for(i=0;i<l;i++)
    {
        int t=str[i]-'a';
        if(p->next[t]==NULL)
        p->next[t]=newnode();
        p=p->next[t];
    }
    p->v=1;
}
int findd(node *root,char *str)
{
    node *p=root;
    int i,l=strlen(str);
    for(i=0;i<l;i++)
    {
        int t=str[i]-'a';
        if(p->next[t]==NULL)
        return 0;
        p=p->next[t];
    }
    return p->v;
}
int main()
{
    char ch[100],str[100][100];
    int i,j,m,kk=1;
    while(~scanf("%d%d",&k,&e))
    {
        node *root=newnode();
        for(i=0;i<k;i++)
        {
            scanf("%s",ch);
            addnode(root,ch);
        }
        getchar();
        int maxx=0;
        for(i=0;i<e;i++)
        {
            fgets(str[i],100,stdin);
            int l=strlen(str[i]);
            m=0;
            cnt=0;
            for(j=0;j<l;j++)
            {
                if((str[i][j]>='a'&&str[i][j]<='z')||(str[i][j]>='A'&&str[i][j]<='Z'))
                {
                    if(str[i][j]>='A'&&str[i][j]<='Z')
                    ch[m++]=str[i][j]+32;
                    else ch[m++]=str[i][j];
                }
                else
                {
                    ch[m]=0;
                    m=0;
                    if(findd(root,ch))
                    cnt++;
                }
            }
            if(maxx<cnt)
            maxx=cnt;
            num[i]=cnt;
        }
        printf("Excuse Set #%d\n",kk++);
        for(i=0;i<e;i++)
        {
            if(num[i]==maxx)
            printf("%s",str[i]);
        }
        printf("\n");
    }
    return 0;
}

 Excuses, Excuses! 

Judge Ito is having a problem with people subpoenaed for jury duty giving rather lame excuses in order to avoid serving. In order to reduce the amount of time required listening to goofy excuses, Judge Ito has asked that you write a program that will search for a list of keywords in a list of excuses identifying lame excuses. Keywords can be matched in an excuse regardless of case.

Input

Input to your program will consist of multiple sets of data.

  • Line 1 of each set will contain exactly two integers. The first number ( tex2html_wrap_inline30 ) defines the number of keywords to be used in the search. The second number ( tex2html_wrap_inline32 ) defines the number of excuses in the set to be searched.
  • Lines 2 through K+1 each contain exactly one keyword.
  • Lines K+2 through K+1+E each contain exactly one excuse.
  • All keywords in the keyword list will contain only contiguous lower case alphabetic characters of length L ( tex2html_wrap_inline42 ) and will occupy columns 1 through L in the input line.
  • All excuses can contain any upper or lower case alphanumeric character, a space, or any of the following punctuation marks [SPMamp“.,!?&] not including the square brackets and will not exceed 70 characters in length.
  • Excuses will contain at least 1 non-space character.

Output

For each input set, you are to print the worst excuse(s) from the list.

  • The worst excuse(s) is/are defined as the excuse(s) which contains the largest number of incidences of keywords.
  • If a keyword occurs more than once in an excuse, each occurrance is considered a separate incidence.
  • A keyword “occurs” in an excuse if and only if it exists in the string in contiguous form and is delimited by the beginning or end of the line or any non-alphabetic character or a space.

For each set of input, you are to print a single line with the number of the set immediately after the string “Excuse Set #“. (See the Sample Output). The following line(s) is/are to contain the worst excuse(s) one per line exactly as read in. If there is more than one worst excuse, you may print them in any order.

After each set of output, you should print a blank line.

Sample Input

5 3dogatehomeworkcanarydiedMy dog ate my homework.Can you believe my dog died after eating my canary... AND MY HOMEWORK?This excuse is so good that it contain 0 keywords.6 5superhighwaycrazythermonuclearbedroomwarbuildingI am having a superhighway built in my bedroom.I am actually crazy.1234567890.....,,,,,0987654321?????!!!!!!There was a thermonuclear war!I ate my dog, my canary, and my homework ... note outdated keywords?

Sample Output

Excuse Set #1Can you believe my dog died after eating my canary... AND MY HOMEWORK?

Excuse Set #2I am having a superhighway built in my bedroom.There was a thermonuclear war!

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115320.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • c++ char数组初始化_二维字符串数组初始化

    c++ char数组初始化_二维字符串数组初始化chars[10]=”Hello”;//剩余全用0填充chars[10]={‘H’,’e’,’l’,’l’,’o’,’\0′};//和上面效果一样chars[10]={‘H’,’e’,’l’,’l’,’o’};//和前面效果一样chars[10]={0}//全部初始化为0chars[10]=”Hello,world.\n”;//超出部分丢…

  • 网页返回顶部的几种方法

    网页返回顶部的几种方法

  • 阅读书源最新2020在线导入_最最最最最好用的小说神器,全网书源免费用!

    阅读书源最新2020在线导入_最最最最最好用的小说神器,全网书源免费用!今天给大家分享的是小说软件,为了满足所有小伙伴的需求,今天安卓和苹果都安排上了,一款Android应用,一款iOS应用。两款应用都十分相似,都是可以自行添加书源的软件,几乎覆盖全网小说。阅读(Android)软件本身是没有任何资源的,如果不添加书源地址,也不能搜索到任何小说。书源添加流程:软件想要很好的使用,还需要添加书源,该软件自己有一个在线书源库,内含上千个书源地址,足够满足大家的使…

  • 流程图的绘图规范_流程图绘制的基本规则

    流程图的绘图规范_流程图绘制的基本规则画了多年的流程图,你真的画规范了吗?|人人都是产品经理流程有哪些作用?我们为什么要画流程图呢?正确的画流程图规范是什么?流程图是一个很强大的工具,在我们的日常工作中经常会使用到。但我们也发现,有时看到别人流程图的画法、规范都不太一样,这是为什么呢?难道流程图就没有统一的标准或规范吗?基于这个疑问,我出于好奇认http://www.woshipm.com/zhichang/2329530.html以上为笔记来源出!一、流程图的符号要求 有几个重要且常用的符号:…

    2022年10月27日
  • 代码农民提高生产力

    代码农民提高生产力

  • 盘点分布式文件存储系统

    盘点分布式文件存储系统在项目的数据存储中,结构化数据通常采用关系型数据库,非结构化数据(文件)的存储就有很多种方式,服务器本地存储、Nas挂载、ftp等等,今天就来盘点一下,分布式文件存储系统。

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号