好儿郎-志在四方 2015-11-13 04:54 采纳率: 100%
浏览 1809
已采纳

ACM编程题,找出敏感词串,并删除,要求时间和空间效率很高,我写的程序通不过,

Censor
frog is now a editor to censor so-called sensitive words (敏感词).

She has a long text p. Her job is relatively simple -- just to find the first occurence of sensitive word w and remove it.

frog repeats over and over again. Help her do the tedious work.

Input
The input consists of multiple tests. For each test:

The first line contains 1 string w. The second line contains 1 string p.

(1≤length of w,p≤5⋅106, w,p consists of only lowercase letter)

Output
For each test, write 1 string which denotes the censored text.

Sample Input
abc
aaabcbc
b
bbb
abc
abSample Output
a

ab

    上面是题目,大致要求:
    W串是可疑串,P是输入串,在P中将出现的W串删除,然后输出P串;
    下面是我写的代码:
    #include<iostream>

#include
using namespace std;

int main()
{
string s1,s2; //s1用于做可疑串,s2用于做输入串
while(cin>>s1)
{
cin>>s2;

    while(-1!=s2.find(s1))  //s2字符串中存在可疑串 
    {

        s2.erase(s2.find(s1),s1.size());
    }
    cout<<s2<<endl;
}

return 0;

}
图片说明
求大神编写一个C++程序,运行时间很低的程序,谢谢各位大牛了;

  • 写回答

3条回答 默认 最新

  • BoostZ 2015-11-13 05:33
    关注

    建议你问这类时空要求高的ACM问题时把题目要求的时限和空间也说出来,这样也方便别人根据要求选择合适的算法。
    这道题属于字符串匹配问题,你可以看看**KMP算法**,如果时间还是达不到的话就用**Boyer-Moore算法**吧。代码就自己搞定喽,做ACM还是尽量不要看别人的代码比较好

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(2条)

报告相同问题?

悬赏问题

  • ¥30 Matlab打开默认名称带有/的光谱数据
  • ¥50 easyExcel模板 动态单元格合并列
  • ¥15 res.rows如何取值使用
  • ¥15 在odoo17开发环境中,怎么实现库存管理系统,或独立模块设计与AGV小车对接?开发方面应如何设计和开发?请详细解释MES或WMS在与AGV小车对接时需完成的设计和开发
  • ¥15 CSP算法实现EEG特征提取,哪一步错了?
  • ¥15 游戏盾如何溯源服务器真实ip?需要30个字。后面的字是凑数的
  • ¥15 vue3前端取消收藏的不会引用collectId
  • ¥15 delphi7 HMAC_SHA256方式加密
  • ¥15 关于#qt#的问题:我想实现qcustomplot完成坐标轴
  • ¥15 下列c语言代码为何输出了多余的空格