当前位置: 代码迷 >> 综合 >> 蓝桥杯 ADV-198 VIP试题 P1003(试题解析)
  详细解决方案

蓝桥杯 ADV-198 VIP试题 P1003(试题解析)

热度:52   发布时间:2024-01-21 20:04:12.0

试题 算法提高 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;
}