洛谷p4824 Censoring S
k
m
p
+
栈
kmp+栈
kmp+栈
题目链接
题目大意
给定字符串 a , b a,b a,b，在 a a a中不断删除 b b b，直到 a a a中没有完整的字符串 b b b，输出最终操作之后的 a a a
思路
用
k
m
p
kmp
kmp在
a
a
a中匹配
b
b
b，用栈进行删除操作
进行
k
m
p
kmp
kmp时，把下标
i
i
i入栈，匹配成功时执行出栈操作，更新
j
j
j到当时
i
i
i能匹配到最大位置开始再
k
m
p
kmp
kmp
ACcode
#include<bits/stdc++.h>
using namespace std;
const int M = 1e6 + 9;
int pmt[M], f[M], stk[M];
void get_pmt(const string& s, const string& p) {
for (int i = 1, j = 0;i < p.size();i++) {
while (j && p[i] != p[j])j = pmt[j - 1];
if (p[i] == p[j])j++;
pmt[i] = j;
}
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
string s, p;cin >> s >> p;
get_pmt(s, p);
int top = 0;
for (int i = 0, j = 0;i < s.size();i++) {
while (j && s[i] != p[j])j = pmt[j - 1];
if (s[i] == p[j])j++;
f[i] = j;
stk[++top] = i;
if (j == p.size()) {
top -= p.size();
j = f[stk[top]];
}
}
for (int i = 1;i <= top;i++)cout << s[stk[i]];
return 0;
}