好儿郎-志在四方 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条)

报告相同问题?

悬赏问题

  • ¥15 咨询一下有关于王者荣耀赢藏战绩
  • ¥100 求购一套带接口实现实习自动签到打卡
  • ¥50 MacOS 使用虚拟机安装k8s
  • ¥500 亚马逊 COOKIE我如何才能实现 登录一个亚马逊账户 下发新 COOKIE ..我使用下发新COOKIE 导入ADS 指纹浏览器登录,我把账户密码 修改过后,原来下发新COOKIE 不会失效的方式
  • ¥20 玩游戏gpu和cpu利用率特别低,玩游戏卡顿
  • ¥25 oracle中的正则匹配
  • ¥15 关于#vscode#的问题:把软件卸载不会再出现蓝屏
  • ¥15 vimplus出现的错误
  • ¥15 usb无线网卡转typec口
  • ¥30 怎么使用AVL fire ESE软件自带的优化模式来优化设计Soot和NOx?