试题 算法提高 P1003
提交此题 评测记录
资源限制
时间限制：1.0s 内存限制：256.0MB
作为一名网络警察，你的任务是监视电子邮件，看其中是否有一些敏感的关键词。不过，有些狡猾的犯罪嫌疑人会改变某些单词的字母顺序，以逃避检查。请编写一个程序，发现这种调整过顺序的关键词。程序的输入有两行，第一行是关键词列表，第二行是待检查的句子。程序的输出为在该句子中所找到的经过顺序调整的关键词。（单词全部为小写，单词之间以一个空格分隔，每一行的单词个数不限）
输入：
guns mines missiles
aameric ssell snug dan iimsssle ot sit neeemis
输出：
guns missiles
解题思路：本题关键，如何读取每一行中以空格划分的单词，这里我提供了两种不同的方法，详见divideSen 和 getSingleWord 函数；以及如何 判断 关键词和乱序的待检查单词是否相等，详见 isSameLetter 函数。
AC代码如下：
#include <iostream>
#include <vector>
#include <string.h>
#include <sstream>
#include <algorithm>
using namespace std;
vector<string> KWS;
vector<string> TXT;
int agc[65535]; //第i个关键字是否出现在文本中 ：0，未出现；1，出现
void divideSen(string kw){// 处理string 读取单词
int len=kw.size();
int S=0,E=0;
for(int i=0;i<len;i++){
if( (i-1<0 || kw[i-1]==' ') && kw[i]!=' ' ){
S=i;
}
if( (i+1>=len || kw[i+1]==' ') && kw[i]!=' ' ){
E=i;
string tmp=kw.substr(S,E-S+1);
KWS.push_back(tmp);
}
}
}
void getSingleWord(string kw){//字符串流 读取单词
string tp;
istringstream iss(kw);
while(iss>>tp){
TXT.push_back(tp);
}
}
bool isSameLetter(string test,string tmk){
int len1=test.size();
int len2=tmk.size();
if(len1==len2){
for(int i=0;i<len1;i++){
char c=test[i];
for(int j=i;j<len1;j++){
if(i!=j && tmk[j]==c){
swap(tmk[j],tmk[i]);
break;
}
}
}
// cout<<test<<" , "<<tmk<<endl;
if(test==tmk)
return true;
else
return false;
}
else
return false;
}
void isAllergic(string test){
for(int i=0;i<KWS.size();i++){
string tmk=KWS[i];
if( isSameLetter(test,tmk) ){
agc[i]=1;
break;
}
}
}
int main(int argc, char** argv) {
string keyWords;
getline(cin,keyWords);
divideSen(keyWords);
string context;
getline(cin,context);
getSingleWord(context);
int len=KWS.size();
memset(agc,0,sizeof(agc));
for(int i=0;i<TXT.size();i++){
string test=TXT[i];
isAllergic(test);
}
for(int i=0;i<len;i++){
if(agc[i]==1)
cout<<KWS[i]<<" ";
}
return 0;
}