共计 3830 个字符，预计需要花费 10 分钟才能阅读完成。
#include <bits/stdc++.h>
#include <cstdio>
#define input(n) cin>>n
#define print(n) cout<<n<<endl
// 我在这里～
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
#define int long long
typedef long long ll;
// 变量定义~
string a, b;
int len_a, len_b;
int st[1000005];
int cha[10000005];
int sums[10000005];
int last_j[1000005];
int ans;
bool debug = false;
void preload() {
int j=0;
st[0] = 0;
for (int i=1; i < len_b; i++) {
while (j > 0 && b[j] != b[i]) j = st[j-1];
if (b[j] == b[i]) j++;
st[i] = j;
}
}
void cout_sum() {
cout << "ind : [ ";
for (int i=0; i < len_a; i++) {
cout << i << " ";
}
cout << "]" << endl;
cout << " a : [";
for (int i=0; i < len_a; i++) {
cout << a[i] << " ";
}
cout << "]" << endl;
cout << "sums: [";
for (int i=0; i < len_a; i++) {
cout << sums[i] << " ";
}
cout << "]" << endl;
cout << "cha : [";
for (int i=0; i < len_a; i++) {
if (cha[i] == -1) cout << "-" << " ";
else cout << cha[i] << " ";
}
cout << "]" << endl;
cout << "last: [";
for (int i=0; i < len_a; i++) {
cout << last_j[i] << " ";
}
cout << "]" << endl;
}
void kmp() {
int i, j=0;
int p=-1;
int last=0;
int cnt2=0;
for (i=0; i < len_a; i++) {
if (i != 0) {
sums[i] = sums[i-1] + cha[i];
}
if (sums[i] > 0) {
last_j[i] = 0;
if (debug) cout << endl;
continue;
}
while (j > 0 && b[j] != a[i]) {
j = st[j-1];
}
if (debug) cout << i << " " << j << endl;
if (b[j] != a[i]){
last = i;
if (debug) cout << "Set last to " << last << endl;
}
last_j[i] = j;
if (b[j] == a[i]) {
j++;
}
if (j == len_b) {
p = i;
int cnt=1;
while (cnt < len_b) {
p--;
if (sums[p] == 0) cnt++;
}
cha[p]++;
if (p == 0) {
sums[p] = cha[p];
}
cha[i+1]--;
// j = 0;
// if (i < len_b) {
// sums[len_b-1] = 1;
// i = 1;
// }
// else {
i = p-2;
while (i >= 0 && sums[i+1] > 0) i--;
i = max((ll)(-1), i);
// }
j = last_j[i+1];
if (debug) cout << "i back to " << i+1 << endl;
if (debug) cout << "j back to " << j << endl;
// i++;
}
if (debug) cout_sum();
cnt2++;
// if (cnt2 > 20) break;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
// freopen("../data6.in", "r", stdin);
// freopen("../datanow.out", "w", stdout);
cin >> a >> b;
len_b = b.size();
memset(st, 0, sizeof st);
preload();
// do {
len_a = a.size();
ans = 0;
kmp();
// if (ans == 0) break;
// for (int i=ans; i >= 1; i--) {
// a.erase(haved[i], len_b);
// }
for (int i=0; i < len_a; i++) {
if (sums[i] == 0) cout << a[i];
}
// cout << a << endl;
// } while (ans != 0);
cout << endl;
return 0;
}
正文完
