[字符串匹配][排序应用]小海的困惑
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]);
}
}
}
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读