P7674 [COCI2013-2014#5] EKSPLOZIJA 题解

· · 题解

0.题目大意：

这道题题意已经十分简洁，我就不再过多赘述了。

1.思考过程：

首先看到数据范围，发现 1≤ 原字符串长度 ≤10^6，我不禁倒吸一口凉气：暴力做不了了。

为什么不行呢？因为这题不仅仅是要求子串，关键是删完子串后还要合并，这个时间是 O(n^2) 级别的。

看到这，你知道怎么做了吗？

哦，我听到有人说用栈。没错，这道题我就给大家用栈来做一做。

2.分析：

首先我们需要一个 st[] 数组，用于记录放入栈的字符；我们还需要一个 w[] 数组，用于记录放入栈的字符是在子串中的位置，即第几个。

接下来我们开始从头遍历原字符串。如果我们发现此时遍历的字符既不是子串的第一个字符，也不是子串的 w[top]+1 位，即没有连着前面的字符，则栈内元素全部输出，再输出当前字符。

如果满足当中任意一个条件，则放入栈中。如果发现此字符的位置已是子串的结尾字符，则直接将 top 减掉。

最后，如果栈内还有字符，说明这些是最后未被删除的，也应输出。

3.正确代码

不要抄袭哦~

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
char st[1000005];
int l1,l2,top,w[1000005];
int main(){
    ios::sync_with_stdio(false);
    cin>>s1>>s2;
    l1=s1.size();
    l2=s2.size();
    s2=" "+s2;
    bool ok=0;
    for(int i=0;i<l1;i++){
        if(s1[i]!=s2[w[top]+1]&&s1[i]!=s2[1]){
            for(int j=1;j<=top;j++){
                cout<<st[j];
            }
            top=0;
            cout<<s1[i];
            ok=1;
//          cout<<top<<" "<<s1[i]<<" "<<111111<<endl;
            continue;
        }
        st[++top]=s1[i];
        if(s1[i]!=s2[w[top-1]+1]){
            w[top]=1;
        }
        else{
            w[top]=w[top-1]+1;
        }
        if(w[top]==l2){
            top-=l2;
        }
//      cout<<top<<" "<<s1[i]<<endl;
    }
    for(int i=1;i<=top;i++){
        cout<<st[i];
        ok=1;
    }
    if(!ok) cout<<"FRULA";
    return 0;
}

4.写在后面：

本蒟蒻的第一篇题解，望过，谢谢！