专栏首页陈黎栋的专栏啦[字符串匹配][排序应用]小海的困惑

[字符串匹配][排序应用]小海的困惑

1482小海的困惑

题目描述

给定一些关键词,按照关键词在文本中出现的位置,排序输出。

输入

输入的第一行为两个正整数M(0<M<=20) N(0<N<=10000) 分别代表了关键词的个数,以及文本的字符个数。用空格隔开。接下来一行是源文本,其中有N个字符。都是英文字符,大小写敏感。然后为M行,每行为一个数字和一个单词,用空格隔开,分别代表关键词的字符个数K(0<K<=1000)以及关键词。

输出

输出文本中出现的关键词,中间用空格隔开。(按照首次出现的位置从小到大排列输出结果)

样例输入

5 65 mynameiscaishenghooIwanttoplaycomputergamesIdonotlikeappleshoohoa 6 father 5 apple 4 want 8 caisheng 6 hoohoa

样例输出

caisheng want apple hoohoa

解法:

m个关键词存在一个数组A[]中,在开一个空间为m的数组B[]记录每个关键词第一次出现的位置(这是一个字符串匹配问题,可以用【KMP算法优化】)。

然后是一个【排序问题】,使用冒泡排序对B[]排序,每一趟记录最小的那个元素B[index]的初速index,然后输出A[index].

文本没有空格? 因为我的代码通过了测试,所以应该是没有空格的。

以下是暴力解法:

import java.util.Arrays;
import java.util.Scanner;
publicclass Main
{
publicstaticvoid main(String args[])
      {
            Main p=new Main();
            Scanner cin=new Scanner(System.in);
intn=0,m,i,j;
m=cin.nextInt();//number of key word
n=cin.nextInt();// len of text
            String text;
intlen[] = newint[m];
            String keyword[] = new String[m];
            String summary[] = new String[n];
intindex[] = newint[m];//关键词首次出现的位置
            Arrays.fill(summary,null);
text = cin.next();
for(i=0;i<m;i++){
 len[i] = cin.nextInt();
 keyword[i] = cin.next();
            }
for(i=0;i<m;i++){//遍历关键词
 for(j=0;j<= n -len[i];j++){//遍历文本
 if(text.substring(j, j+len[i]).equals(keyword[i])){
 summary[j] = keyword[i];    //j记录首次出现的位置
 break;
                    }
                }         
            }
booleanflag = true;
for(j=0;j<n;j++){
 if(summary[j]!=null){
 if(flag){
                        System.out.print(summary[j]);
 flag = false;
                    }
 else{
                        System.out.print(" "+summary[j]);
                    }
                }
            }
      }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Java Code review 一些原则的原因探讨

    陈黎栋
  • [每周看]代码优化技巧·代码编写好习惯·代码规范

    明确一个概念,对方法的调用,即使方法中只有一句语句,也是有消耗的,包括创建栈帧、调用方法时保护现场、调用方法完毕时恢复现场等。所以例如下面的操作:

    陈黎栋
  • OpenKG数据逐一截图说明

    可能与三元组相关的标签(一个数据集可能有多个标签)的总计数为 51,不算特别多,所以我打算把每个数集看一下,看看有没有 满足大小在 1G-10G

    陈黎栋
  • 程序员你为什么这么累【续】:编码习惯-函数编写建议

    之前系列文章里面完整的代码已经上github,地址在文章最后 傻瓜都能写出计算机可以读懂的代码,只有优秀的程序员才能写出人能读懂的代码! 在我看来,编写简单的函...

    程序猿DD
  • 用eosjs接入eos主网

    用eosjs连接主网节点很简单,只需要在创建JsonRpc对象时,指定要连接主网节点的地址 就可以了。

    用户1408045
  • 互联网移动端即将进入“暗黑时代”

    2019-5-7 Google I/O 2019 Android Q发布 - 推出暗色模式

    用户5521279
  • Spring Boot 2.x(十六):玩转vue文件上传

    最近用到了Vue + Spring Boot来完成文件上传的操作,踩了一些坑,对比了一些Vue的组件,发现了一个很好用的组件——Vue-Simple-Uploa...

    山禾说
  • 忽略Minecraft中不完美的演示下分层的深度Q网络

    RockNPeng
  • TMQ微信沙龙第一期回顾

    Android流畅度原理&优化 活动时间:2016年5月26日 活动介绍:微信线上交流群活动介绍TMQ微信沙龙第一期分享圆满结束啦~本次分享的主题是Androi...

    腾讯移动品质中心TMQ

扫码关注云+社区

领取腾讯云代金券