C++14(g++5.4) 解法, 执行用时: 110ms, 内存消耗: 12012K, 提交时间: 2019-12-08 22:14:48

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

int main() {
  string S; cin >> S;
  string T; cin >> T;
  vector<int> next(T.size(), -1);
  for (int i = 1; i < T.size(); i++) {
    int j = next[i - 1];
    while (j != -1 && T[i - 1] != T[j]) j = next[j];
    next[i] = j + 1;
  }

  int j = 0;
  stack<int> J;
  string K;
  for (int i = 0; i < S.size(); i++) {
    K.push_back(S[i]);
    while (j != -1 && S[i] != T[j]) j = next[j];
    J.push(++j);
    if (j == T.size()) {
      for (int k = 0; k < T.size(); k++) K.pop_back(), J.pop();
      j = J.empty()?0:J.top();
    }
  }
  cout << K << endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 27ms, 内存消耗: 13936K, 提交时间: 2022-09-09 18:20:20

#include<cstdio>
#include<cstring>
char a[1000010],b[1000010];
int na[1000010],nb[1000010],st[1000010],c=0;
int main()
{
	scanf("%s %s",a+1,b+1);
	int n=strlen(a+1),m=strlen(b+1),t;
	for(int i=2,j=0;i<=m;i++)
	{
		while(j&&b[j+1]!=b[i])j=nb[j];
		if(b[j+1]==b[i])++j;
		nb[i]=j;
	}
	for(int i=1,j=0;i<=n;i++)
	{
		while(j&&a[i]!=b[j+1])j=nb[j];
		if(a[i]==b[j+1])++j;
		na[i]=j;
		st[++c]=i;
		if(j==m)c-=m,j=na[st[c]];
	}
	for(int i=1;i<=c;i++)printf("%c",a[st[i]]);
	return 0;
}