洛谷 P4824 分析（别看）

科技起源的小号1

2026-08-27 10:09:41

发布于：天津

2阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体字符串

1.2 题目背景、允许、禁止与限制

背景：
有一个大字符串 $S$ 和小子串 $T$
允许：
需要反复找到 $S$ 中包含的第一个 $T$ ，然后把它删除
限制：
有可能 $S$ 删除完毕之后会产生新的 $T$ ，也可能同时存在多个 $T$

1.3 题目数据范围与猜测

$1 \le |S| \le 10^6 \rightarrow O(|S|^2\times |T|)$

1.4 一句话概括题意

重复删除大字符串中第一次出现的小子串，直到不存在这样的子串

2 题目破题推导

2.1 大拆小，小组大

一步步来，先考虑暴力：
暴力的缺陷就是在于每次匹配不成功，大串和子串都要从头开始重新匹配。
那么有没有什么方法可以避免这种情况呢？这种情况发生的主要原因就是因为我不知道需要回退到哪里，因此为了避免回退的不够多导致无法匹配，只得从头开始
接下来我们就思考如何设置回退的长度，使得既能不浪费时间，还能正确实现？
先想如果快速实现的话，逻辑应该是怎样的：
应该是一直匹配匹配...，突然到某一位的时候发现匹配长度 $=$ 目标子串长度，这时候我们将子串匹配状态退回到“把子串删除后主串那个位置匹配了多少位子串”，主串不退回
你发现了吗，这样既能满足时间复杂度 $O(|S|)$ ，又能满足正确匹配

3 模型匹配

kmp计算回退长度
栈，因为需要回退不定长度，因此普通栈时间开销很大，因此需要数组模拟栈
栈是干嘛的呢？因为添加和删除可以看成是后进先出，所以栈记录的是字符串中的下标

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

string s1, s2;
const int N = 1e7 + 10;
int nxt[N];
int top = 0;
int s[N];
int f[N];

int main(){

    cin >> s1 >> s2;
    int la = s1.size(), lb = s2.size();
    s1 = " " + s1;
    s2 = " " + s2;
    for (int i = 2, j = 0;i <= lb;i++){
        while(j > 0 && s2[i] != s2[j + 1]){
            j = nxt[j];
        }
        if (s2[i] == s2[j + 1]){
            j++;
        }
        nxt[i] = j;
    }
    for (int i = 1, j = 0;i <= la;i++){
        while(j > 0 && s1[i] != s2[j + 1]){
            j = nxt[j];
        }
        if (s1[i] == s2[j + 1]){
            j++;
        }
        f[i] = j;
        s[++top] = i;
        if (j == lb){
            top -= lb;
            j = f[s[top]];
        }
    }
    for (int i = 1;i <= top;i++){
        cout << s1[s[i]];
    }
    
    return 0;
}