C++14(g++5.4) 解法, 执行用时: 39ms, 内存消耗: 14968K, 提交时间: 2019-12-12 12:19:11

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

const int MAXN = 1e5;

struct Node {
  int ch[26];
  int fail;
  int last;
  int val;
};
Node nodes[MAXN];
int sz;
int N;
string words[MAXN];


void insert(string s, int idx) {
  int cur = 0;
  for (auto ch: s) {
    int &nxt = nodes[cur].ch[ch-'a'];
    if (nxt == 0) nxt = ++sz;;
    cur = nxt;
  }
  nodes[cur].val = idx;
}

void build() {
  queue<int> Q; Q.push(0);
  while (!Q.empty()) {
    auto s = Q.front(); Q.pop();
    for (int i = 0; i < 26; i++) {
      int &t = nodes[s].ch[i];
      int f = nodes[s].fail;
      if (t == 0) t = nodes[f].ch[i];
      else {
        while (f && !nodes[f].ch[i]) f = nodes[f].fail;
        nodes[t].fail = !s?0: nodes[f].ch[i];
        nodes[t].last = nodes[t].val?nodes[t].val:nodes[nodes[t].fail].last;
        Q.push(t);
      }
    }
  }
}
int main() {
  string S; cin >> S;
  cin >> N;
  for (int i = 1; i <= N; i++) cin >> words[i];
  for (int i = 1; i <= N; i++) insert(words[i], i);
  build();
  string T;
  stack<int> st;
  st.push(0);
  int cur = 0;
  for (auto ch: S) {
    int id = ch - 'a';
    cur = nodes[cur].ch[id];
    T.push_back(ch);
    st.push(cur);
    // cout << ch << " " << cur << " " << nodes[cur].last << endl;
    if (nodes[cur].last) {
      int k = nodes[cur].last;
      // cout << words[k] << endl;
      for (int j = 0; j < words[k].size(); j++) T.pop_back(), st.pop();
      cur = st.top();
    }
  }
  cout << T << endl;
}

C++(clang++ 11.0.1) 解法, 执行用时: 21ms, 内存消耗: 12536K, 提交时间: 2023-02-24 18:03:59

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int SZ = 1e6+10;
char str[N], s[N];
int n, fail[SZ];
int trie[SZ][30],tot = 1,End[SZ];
void Insert(const char* s){
	int len = strlen(s), p = 1;
	for(int i = 0;i < len;i++){
		int ch = s[i]-'a';
		if(!trie[p][ch]) trie[p][ch] = ++tot;
		p = trie[p][ch];
	}
	End[p] = len;
}
queue<int> q;
void getFail(){
	for(int i = 0;i < 26;i++) trie[0][i] = 1;
	q.push(1); fail[1] = 0;
	while(!q.empty()){
		int p = q.front(); q.pop();
		for(int i = 0;i < 26;i++){
			if(!trie[p][i]) trie[p][i] = trie[fail[p]][i];
			else{
				q.push(trie[p][i]); 
				fail[trie[p][i]] = trie[fail[p]][i];
			}
		}
	}
}
char path[N];
int top = 0,Stack[N];
void solve(){
	getFail();	//为什么非要更新Fail数组呢 
	int len = strlen(str);
	for(int i = 0,p = 1;i < len;i++){
		int ch = str[i]-'a';
		p = trie[p][ch];
		Stack[++top] = p; path[top] = str[i];
		if(End[p]) top -= End[p], p = Stack[top];
	}	
	for(int i = 1;i <= top;i++) putchar(path[i]);
}
int main(){
	scanf("%s",str);
	scanf("%d",&n);
	for(int i = 1;i <= n;i++){
		scanf("%s",s); Insert(s);
	}
	solve();
	return 0;
}