Luogu P4824 [USACO15FEB]Censoring (Silver) 审查(银)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define
#define

using namespace std;
typedef long long ll;
struct node {
  int son[26], fail, end;
}t[A];
int n, tot, sta1[A], sta2[A], top;
char s[A], ss[A];
void insert(char *s, int id = 0, int rt = 0) {
  id = strlen(s);
  for (int i = 0; s[i]; i++) {
    int x = s[i] - 'a';
    if (!t[rt].son[x]) t[rt].son[x] = ++tot;
    rt = t[rt].son[x];
  }
  t[rt].end = id;
}
void gfail() {
  queue<int> q;
  for (int i = 0; i < 26; i++) if (t[0].son[i]) q.push(t[0].son[i]);
  while (!q.empty()) {
    int fr = q.front(); q.pop();
    for (int i = 0; i < 26; i++)
      if (t[fr].son[i]) {
        t[t[fr].son[i]].fail = t[t[fr].fail].son[i];
        q.push(t[fr].son[i]);
      }
      else t[fr].son[i] = t[t[fr].fail].son[i];
  }
}
void acm(char *s, int rt = 0) {
  for (int i = 0; s[i]; i++) {
    int x = s[i] - 'a';
    rt = t[rt].son[x];
    sta1[++top] = rt;
    sta2[top] = i;
    while (t[rt].end) top -= t[rt].end, rt = top ? sta1[top] : 0;
  }
  for (int i = 1; i <= top; i++) cout << s[sta2[i]]; puts("");
}

int main(int argc, char const *argv[]) {
  cin >> s; cin >> ss; insert(ss); gfail(); acm(s);
}