P4824 [USACO15FEB] Censoring S

题目链接:https://www.luogu.com.cn/problem/P4824

kmp+栈

栈处理字符串问题有一道入门题:https://www.luogu.com.cn/problem/AT_abc328_d
实际上处理方式就是用数组模拟栈.在遍历字符串的过程中我们时刻监测,对未达到条件的字符我们进行压栈操作,然后如果说遇到了符合条件的字符就减去栈中的这一部分,然后对后面的字符继续重复上述操作.最后只需要输出一整个栈就行.

abc328d的参考代码:

#define maxn 200010
char stk[maxn];
int tp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    string s;
    cin>>s;
    for(int i=0;i<s.size();i++)
    {
        stk[++tp]=s[i];
        if(stk[tp]=='C'&&stk[tp-1]=='B'&&stk[tp-2]=='A')
        {
            tp-=3;
        }
    }
    for(int i=1;i<=tp;i++)
    {
        cout<<stk[i];
    }
}

那么有了上一道题的经验,在这道题中我们也可以用相同的方式去监测和删除.
只不过这题需要删除的子串是一个长度范围为1-1e6的字符串,如果继续用上面这种暴力的监测方式时间复杂度最坏会达到 \(O(n^{2})\)
在这里我们考虑把监测方式从暴力改为kmp.运用kmp的匹配操作完成监测,可以把时间复杂度优化成线性的.
栈发挥的作用和上一道题基本一致,由于删除操作会导致单个字符左右相邻的字符的变动.所以我们需要使用一个pos数组,去记录在匹配时,文本串中每个位置在模式串中对应的位置.这样能在删除操作结束时更新模式串的指针位置.

#define maxn 1000010
string s,t;
int stk[maxn],top,pos[maxn];
vector<int> get_nxt(string s)
{
    int n=s.size();
    vector<int> nxt(n);
    for(int i=1,j=0;i<n;i++)
    {
        while(j&&s[i]!=s[j])
        {
            j=nxt[j-1];
        }
        j+=(s[i]==s[j]);
        nxt[i]=j;
    }
    return nxt;
}
void kmp(const string s,const string t)
{
    vector<int> nxt=get_nxt(t);
    for(int i=0,j=0;i<s.size();i++)
    {
        while(j&&s[i]!=t[j]) j=nxt[j-1];
        if(s[i]==t[j]) j++;
        pos[i]=j;
        stk[++top]=i;
        if(j==t.size())
        {
            top-=(int)(t.size());
            j=pos[stk[top]];
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s>>t;
    kmp(s,t);
    for(int i=1;i<=top;i++)
    {
        cout<<s[stk[i]];
    }
}