题目
思路
这题如果暴力做的话,对长度为$n$的字符串,要遍历$n/m$次,则时间复杂度为$O(n\times n/m)$,而$n/m$最大值为$n$($m$取$1$时),故而暴力做的时间复杂度为$O(n^{2})$,$n$能取到$10^{6}$,故而不可暴力做。
这题可以采用栈模拟的思路。
而且是用string
变量模拟栈。
当前面确认没有待删除字符串的时候,我们明确可以不用回头到一开始的位置重新遍历,所以这个栈尽可能维护了不需要删除的字符串。
代码
#include<iostream>
#include<cstring>
using namespace std;
string s,t;
string stk;
int main()
{
cin>>s>>t;
for(auto c:s)
{
stk+=c; //把每个元素依次入栈
while(stk.size()>t.size()&&stk.substr(stk.size()-t.size())==t) //要保证现在的栈长大于待删除字符串的长度,且栈定刚好是要删除的字符串
stk.erase(stk.end()-t.size(),stk.end()); //删除待删除字符串
}
cout<<stk;
return 0;
}