基础字符串算法杂讲

hhce2012 · 2025-12-13 15:18:37 · 算法·理论

::::info[笔者的话] 其实部分题是远古时期写的，所以代码和马蜂会比较杂乱……将就着看吧。 ::::

字典树

::::info[P8306 【模板】字典树]{open} 有 n 个字符串 s_i 和 q 次询问，每一次询问给定一个 t 查询有多少个 i 使得 t 是 s_i 的前缀。 ::::

考虑暴力，我们枚举 i，判断 t 是否是 s_i 的前缀即可。这样是 O(\sum |s_i|) 的。

考虑另一种暴力：我们枚举 t 的位置，然后对于每一个 i，如果在这个位置 s_i 失配，那么直接把 s_i 踢出去。这样的话，如果出现大量难以被筛除的字符串，单次也是 O(\sum |s_i|) 的。

我们发现第二种暴力很有优化前景：如果，有一种数据结构，它：

• 可以把多个前缀相同的字符串压缩到一起
• 可以模拟第二种暴力匹配过程

那么经过这种数据结构优化后暴力二可以在单次 O(|t|) 之内跑完。现在的问题是如何找到这种数据结构。

考虑把所有的字符串全都插入到一棵树上：

（例子使用 \texttt{us, her, she, is, his}）

我们发现，这种数据结构完美地满足了所有要求：

• \texttt{her}$ 和 $\texttt{his}$ 相同的前缀，$\texttt{h}$，被压缩在了同一个节点 $4
• 第二种暴力匹配时，只需要按照边往下走就可以了

那么，如何把这种数据结构建出来呢？

我们考虑逐个插入字符串，并且在插入的过程中维护两条性质。

从根节点出发：

如果当前节点走一条当前字符的边到达的节点不存在，那么新开一个节点，这样可以保证第二种暴力时冲到这个节点之后走这个字符可以到达当前字符串；

然后，走一条当前字符的边，到达一个新节点，这样如果到达的新节点在第一步已经存在，就不会新开一个节点，于是相同的前缀就被压缩了起来，保证了第一个性质。

于是只需要按照上面的方式建立这种结构，然后实现第二种暴力即可。单次询问复杂度 O(|t|)，足以通过本题。

对于统计某一个节点下字符串数量，在插入一个字符串时把经过的每一个节点的权值 + 1，查询时直接输出到达节点的权值即可。

这种数据结构，就叫做字典树（trie）。

::::success[Code]

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

int tg;

void clear() {
    tg++;
}

struct trie {
    struct node {
        int son[128];
        int cnt, tag;
    }arr[3000030];

    int siz = 1;

    void insert(const string &s) {
        int u = 1;
        for(int i = 0; i < s.size(); i++) {
            if(!arr[u].son[s[i]]) {
                arr[u].son[s[i]] = ++siz;
            }
            if(arr[u].tag != tg) {
                arr[u].cnt = 0;
            }
            arr[u].tag = tg;
            arr[u].cnt++;
            u = arr[u].son[s[i]];
        }
        if(arr[u].tag != tg) {
            arr[u].cnt = 0;
        }
        arr[u].tag = tg;
        arr[u].cnt++;
    }

    int query(const string &s) {
        int u = 1;
        for(int i = 0; i < s.size(); i++) {
            if(!arr[u].son[s[i]]) {
                return 0;
            }
            u = arr[u].son[s[i]];
            if(arr[u].tag != tg) {
                arr[u].cnt = 0;
            }
            arr[u].tag = tg;
        }
        return arr[u].cnt;
    }
}Trie;

int t, n, q;
string s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    for(cin >> t; t--; ) {
        clear();
        cin >> n >> q;
        for(int i = 1; i <= n; i++) {
            cin >> s;
            Trie.insert(s);
        }
        for(; q--;) {
            cin >> s;
            cout << Trie.query(s) << '\n';
        }
    }
    return 0;
}

::::

::::info[P10471 最大异或对 The XOR Largest Pair]{open} 有 n 个整数 a_i，求两两之间最大的异或和。 ::::

我们考虑对于每一个 i，计算与之前元素的最大异或和。

考虑贪心，从上往下考虑每一 bit，每一次尝试使这个 bit 为 1（即，如果之前的未被筛除的元素中有一个元素这个 bit 与当前元素的这个 bit 不同，把所有这个 bit 与当前元素的这个 bit 相同的元素筛除）。

咦？筛除？你想起来了什么？

没错！我们直接把所有前面的数当成一个从高位到低位的字符串，然后从上往下模拟这个过程，就可以了，单次复杂度是 O(\log V) 的！

所以我们就使用 trie 过掉了这个题。

::::success[Code]

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

struct trie {
  int ch[33000033][2], cnt = 1;

  void insert(int x) {
    int u = 1;
    for(int i = 31; i >= 0; i--) {
      if(!ch[u][(x >> i) & 1]) {
        ch[u][(x >> i) & 1] = ++cnt;
      }
      u = ch[u][(x >> i) & 1];
    }
  }

  int query(int x) {
    int ans = 0, u = 1;
    for(int i = 31; i >= 0; i--) {
      if(ch[u][((x >> i) & 1) ^ 1]) {
        ans |= (1 << i);
        u = ch[u][((x >> i) & 1) ^ 1];
      }else {
        u = ch[u][(x >> i) & 1];
      }
    }
    return ans;
  }
}tr;

int n, arr[1000010], ans;

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
    tr.insert(arr[i]);
    ans = max(ans, tr.query(arr[i]));
  }
  cout << ans << '\n';
  return 0;
}

::::

KMP

::::info[P3375 【模板】KMP]{open} 字符串匹配，但是要求你输出模式串的 fail 指针。 ::::

fail 指针就是指某一个前缀的最长公共前后缀长度。现在考虑把它求出来，然后着手考虑匹配。

以下设求原串为 s，下标从 0 开始。

考虑一个 i：

• 其余情况，考虑 i - 1，我们发现：
  • 如果 s_{fail_{i - 1} + 1} = s_i，那么 fail_i = fail_{i - 1} + 1，这是显然的；
  • 否则，我们观察现在的状况：我们已经 舍弃掉了前缀 直到 fail_{i - 1}。现在我们 二次舍弃，即考虑 fail_{fail_{i - 1}}：
  • 如果 s_{fail_{fail_{i - 1}} + 1} = s_i，那么 fail_i = fail_{fail_{i - 1}} + 1，这是显然的；
  • ……
• 最后，如果实在没有找到，那么 fail_i = 0，即所有的东西全都被舍弃完了。

终于我们求出了 fail 数组，现在考虑匹配……不对！不是只要把两个字符串加一个 # 拼到一起，然后求一求 fail，检查一下模式串是否全部没有被舍弃，不就可以了吗？

这个很对，这样做是 O(|s + t|) 的。但是有一种复杂度略大但是更好记（至少对我来看是这样的）并且可以与后面的内容做衔接的方法：

我们设 trans_{i, j} 为当前在 i，突然冲进来一个字符 j，最后会到达哪一个节点。很显然，fail_{i + 1} = trans_{fail_i, s_i}。现在考虑如何求 trans。

考虑冲进一个 j：

• 如果 j = s_i，那么我们不用舍弃前缀，即 trans_{i, j} = i + 1；
• 否则，我们得舍弃前缀，即 trans_{i, j} = trans_{fail_i, j}。

这样做是 O(|s|\Sigma) 的。

::::success[Code（fail 指针版本）]

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

int pf[1000010];
string s, t;

void KMP(string &tx, string &pt) {
  for(int i = 1; i < pt.size(); i++) {
    int j = pf[i - 1];
    for(; j && pt[j] != pt[i]; j = pf[j - 1]) {
    }
    if(pt[j] == pt[i]) {
      j++;
    }
    pf[i] = j;
  }
  for(int i = 0, j = 0; i < tx.size(); i++) {
    for(; j && pt[j] != tx[i]; j = pf[j - 1]) {
      //cout << i << ' ' << j << ' ' << pf[j - 1] << '\n';
      //for(int i = 1; i <= 100000000; i++) {
        //1234 / 567;
      //}
    }
    if(pt[j] == tx[i]) {
      j++;
    }
    if(j == pt.size()) {
      cout << i - pt.size() + 2 << '\n';
    }
  }
  for(int i = 0; i < pt.size(); i++) {
    cout << pf[i] << ' ';
  }
  cout << '\n';
}

signed main() {
  cin >> s >> t;
  KMP(s, t);
  return 0;
}

::::

::::success[Code（自动机版本）]

#include <bits/stdc++.h>
#define int long long
#define popc __builtin_popcountll
#define ctz __builtin_ctzll
#define ldouble long double
#define DEBUG
using namespace std;

int l, trans[1000010][26], fail[1000010];
string a, b;

signed main() {
#ifndef DEBUG
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
#endif
  cin >> a >> b;
  l = b.size();
  trans[0][b[0] - 'A'] = 1;
  for(int i = 1; i <= l; i++) {
    for(int j = 0; j < 26; j++) {
      if(i < l && b[i] - 'A' == j) trans[i][j] = i + 1, fail[i + 1] = trans[fail[i]][j];
      else trans[i][j] = trans[fail[i]][j];
    }
  }
  int c = 0;
  for(int i = 0; i < a.size(); i++) {
    c = trans[c][a[i] - 'A'];
    if(c == l) cout << i - l + 2 << '\n';
  }
  for(int i = 1; i <= l; i++) cout << fail[i] << ' ';
  cout << '\n';
  return 0;
}

::::

::::info[CodeForces1721E Prefix Function Queries]{open} 有一个 s，每一次给一个 t，求 s + t 的 fail 指针。 ::::

容易发现自动机版本由于可以向后推进，所以单次加入一个字符是 O(\Sigma) 的。所以直接做就可以了。

::::success[Code]

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

string s, t;
int q, g[1000110][30], p[1000110];

signed main() {
  cin >> s;
  s = ' ' + s;
  g[0][s[1] - 'a'] = 1;
  for(int i = 1; i < s.size(); i++) {
    for(int j = 0; j < 26; j++) {
      if(i < s.size() - 1 && s[i + 1] - 'a' == j) {
        g[i][j] = i + 1;
        p[i + 1] = g[p[i]][j];
      }else {
        g[i][j] = g[p[i]][j];
      }
    }
  }
  for(cin >> q; q--; ) {
    cin >> t;
    for(int j = 0; j < 26; j++) {
      if(t[0] - 'a' == j) {
        g[s.size() - 1][j] = s.size();
        p[s.size()] = g[p[s.size() - 1]][j];
      }
    }
    for(int i = 0; i < t.size(); i++) {
      for(int j = 0; j < 26; j++) {
        if(i < t.size() - 1 && t[i + 1] - 'a' == j) {
          g[i + s.size()][j] = i + s.size() + 1;
          p[i + s.size() + 1] = g[p[i + s.size()]][j];
          //cout << i + s.size() << ' ' << j << ' ' << p[i + s.size()] << ' ' << g[p[i + s.size()]][j] << '\n';
        }else {
          g[i + s.size()][j] = g[p[i + s.size()]][j];
        }
      }
      cout << p[i + s.size()] << ' ';
    }
    for(int j = 0; j < 26; j++) {
      g[s.size() - 1][j] = g[p[s.size() - 1]][j];
    }
    for(int i = 0; i < t.size(); i++) {
      for(int j = 0; j < 26; j++) {
        p[i + s.size()] = g[i + s.size()][j] = 0;
      }
    }
    cout << '\n';
  }
  return 0;
}

::::

::::info[P4391 [BalticOI 2009] Radio Transmission 无线传输]{open} 给你一个字符串，求这玩意的最小周期（即原串是它无限重复之后的前缀）的长度。 ::::

首先给结论，答案为 n - fail_n。那如何证明呢？

充分性是显然的，以下只证必要性。

考虑如下的一种情况（我们可以假设最小周期是一个前缀）：

假设有一个更小周期，它也是一个周期，并且比我们求出的最小周期还要小。

那么，我们显然可以截断最后面刚好一个更小周期，造出一个原串的更长的相等的前缀后缀，这违背了 fail 的定义。所以答案就是 n - fail_n。

::::success[Code]

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

int n, nxt[1000010][26], fail[1000010];
string s;

int main() {
  cin >> n >> s;
  n = s.size();
  s = ' ' + s;
  nxt[0][s[1] - 'a'] = 1;
  for(int i = 1; i <= n; i++) {
    for(int j = 0; j < 26; j++) {
      if(i < n && s[i + 1] - 'a' == j) {
        nxt[i][j] = i + 1;
        fail[i + 1] = nxt[fail[i]][j];
      }else {
        nxt[i][j] = nxt[fail[i]][j];
      }
    }
  }
  cout << n - fail[n] << '\n';
  return 0;
}

::::

::::info[P2375 [NOI2014] 动物园]{open} 给你一个字符串，求对于每一个位置，一直跳 fail，能跳到的字符串长度小于等于起始点字符串长度的 \frac{1}{2} 的节点的数量。 ::::

考虑跳 fail，发现 fail 组成一棵树并且跳 fail 的过程就是跳祖先。所以我们对于每一个 i，找到开始贡献答案的点，然后找到的点的每一个祖先（包括它自己）都会给 i 的答案贡献 1。所以就可以做了。

::::success[Code]

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

const int kMod = (int)(1e9) + 7;

int t, n, fail[1000010], fa[26][1000010], dep[1000010];
string s;

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  for(cin >> t; t--; ) {
    cin >> s;
    n = s.size();
    for(int i = 1; i < n; i++) {
      int j = fail[i - 1];
      for(; j && s[j] != s[i]; j = fail[j - 1]) {
      }
      if(s[j] == s[i]) {
        j++;
      }
      fail[i] = j;
    }
    for(int i = n; i >= 1; i--) {
      fail[i] = fail[i - 1];
    }
    int mlt = 1;
    dep[0] = 1;
    dep[1] = 2;
    for(int i = 2; i <= n; i++) {
      dep[i] = dep[fail[i]] + 1;
      fa[0][i] = fail[i];
      for(int j = 1; j <= 20; j++) {
        fa[j][i] = fa[j - 1][fa[j - 1][i]];
      }
      int cur = i;
      for(int j = 20; j >= 0; j--) {
        if(fa[j][cur] > (i >> 1)) {
          cur = fa[j][cur];
        }
      }
      cur = fail[cur];
      mlt = 1ll * mlt * dep[cur] % kMod;
      //cout << i << ' ' << fail[i] << '\n';
      //cout << i << ' ' << cur << ' ' << dep[i] << ' ' << dep[cur] << '\n';
    }
    for(int i = 0; i <= n; i++) {
      fail[i] = dep[i] = 0;
      for(int j = 0; j <= 20; j++) {
        fa[j][i] = 0;
      }
    }
    cout << mlt << '\n';
  }
  return 0;
}

::::

::::info[CodeForces471D MUH and Cube Walls]{open} 有两个字符串 s 和 t。对于字符串 a 和 b，如果可以给 a 的每一个元素全部加上或者减去一个值使得 a = b，那么称 a 和 b 匹配。求 s 中与 t 匹配的子串数量。 ::::

遇到这种题，直接大力做阶差。做完阶差之后这个题就是板子。

::::success[Code]

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

int n, w, arr[200020], brr[200020], p[400040];

int KMP() {
  for(int i = 1; i < w; i++) {
    int j = p[i - 1];
    for(; j && brr[j] != brr[i]; j = p[j - 1]) {
    }
    if(brr[j] == brr[i]) {
      j++;
    }
    p[i] = j;
    //cout << p[i] << ' ';
  }
  //cout << '\n';
  int ans = 0;
  for(int i = 0, j = 0; i < n; i++) {
    for(; j && brr[j] != arr[i]; j = p[j - 1]) {
      //cout << j << ' ' << brr[j] << ' ' << arr[i] << '\n';
    }
    if(brr[j] == arr[i]) {
      j++;
    }
    if(j == w) {
      ans++;
    }
    //cout << j << '\n';
  }
  //cout << '\n';
  return ans;
}

int main() {
  cin >> n >> w;
  if(w == 1) {
    cout << n << '\n';
    return 0;
  }
  for(int i = 1; i <= n; i++) {
    cin >> arr[i];
  }
  for(int i = 0; i < n - 1; i++) {
    arr[i] = arr[i + 2] - arr[i + 1];
  }
  n--;
  for(int i = 1; i <= w; i++) {
    cin >> brr[i];
  }
  for(int i = 0; i < w - 1; i++) {
    brr[i] = brr[i + 2] - brr[i + 1];
  }
  w--;
  cout << KMP() << '\n';
  return 0;
}

::::

::::info[P3082 [USACO13MAR] Necklace G]{open} 给你一个文本串和一个模式串。求文本串的一个最长的子序列，使得模式串不是它的子串。 ::::

这道题是很经典的自动机上 dp。这种 dp 的状态有 100% 的概率会有一位叫做“当前在节点 ……”。

考虑 dp，设 dp_{i, x} 为文本串匹配了 i 个，当前在模式串的 KMP 自动机的节点 x 上。显然 x \ne M。转移时 dp_{i, x} + 1 \to dp_{i + 1, x}，dp_{i, x} \to dp_{i + 1, trans_{x, s_i}}。

::::success[Code]

//#define DEBUG
#include <bits/stdc++.h>
#ifdef DEBUG
#include <windows.h>
#endif
#define int ll
#define ctz __builtin_ctzll
#define popc __builtin_popcountll
#define lowbit(x) ((x) & -(x))
#define ct1(x) ctz((x) + 1)
using namespace std;
using ll = long long;
const int kMod = int(1e9) + 7, kInf = 0x3f3f3f3f3f3f3f3f;
template<class T>T read(istream &is = cin) {
  T x;
  is >> x;
  return x;
}
int readInt(istream &is = cin) {return read<int>(is);}
int qpow(int x, int y) {
  x %= kMod;
  if(x == 0) return 0;
  int res = 1;
  for(; y; y >>= 1) {
    if(y & 1) res = res * x % kMod;
    x = x * x % kMod;
  }
  return res;
}
int qinv(int x) {return qpow(x, kMod - 2);}
random_device rd;
mt19937_64 mt(rd());

int n, m, trans[1010][26], fail[1010], dp[10010][1010];
string s, t;

signed main() {
#ifndef DEBUG
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
#endif
  cin >> s >> t;
  n = s.size(), m = t.size();
  s = ' ' + s, t = ' ' + t;
  trans[0][t[1] - 'a'] = 1;
  for(int i = 1; i <= m; i++) {
    for(int j = 0; j < 26; j++) {
      if(i < m && t[i + 1] - 'a' == j) trans[i][j] = i + 1, fail[i + 1] = trans[fail[i]][j];
      else trans[i][j] = trans[fail[i]][j];
    }
  }
  for(int i = 0; i < n; i++) {
    for(int j = 0; j < m; j++) dp[i + 1][j] = dp[i][j] + 1;
    for(int j = 0; j < m; j++) if(trans[j][s[i + 1] - 'a'] != m) dp[i + 1][trans[j][s[i + 1] - 'a']] = min(dp[i + 1][trans[j][s[i + 1] - 'a']], dp[i][j]);
  }
  int ans = 12345;
  for(int i = 0; i < m; i++) ans = min(ans, dp[n][i]);
  cout << ans << '\n';
  return 0;
}

::::

子序列自动机

::::info[CSES1087 Shortest Subsequence]{open} 给你一个由 \texttt{ACGT} 组成的字符串，找到最短的字符串，使得它不是给定的字符串的子序列， ::::

考虑验证 s 是否为 t 的子序列的过程，我们发现，每一次会找到 在当前位置之后的第一个匹配下一个字符的字符，然后跳到那里去。那么，能否把这种跳法存储下来，静态处理？

我们可以设 trans_{i, j} 为严格在 i 后面的第一个与 j 匹配的字符。这个东西是容易求的，注意到只需要维护一个 next_j 表示下一个 j 出现的位置即可。如上的东西，就叫子序列自动机。

但是你讲了这么多我题还是不会做啊？

别急。考虑 s 不是 t 的子序列，发现这样子会跳到一个不存在的地方，所以直接设 dp_i 为从 i 跳进不存在的地方的最小代价，做就可以了。

::::success[Code]

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

int g[1000010][30], n, nxt[30], dp[1000010], t, zy[1000010];
string s;

void solve() {
  cin >> s;
  n = s.size();
  fill(dp, dp + n + 1, 10000000);
  s = '#' + s;
  for(int j = 0; j < 26; j++) {
    g[n + 1][j] = n + 1;
  }
  fill(nxt, nxt + 29, n + 1);
  for(int i = n; i >= 0; i--) {
    for(int j = 0; j < 26; j++) {
      g[i][j] = nxt[j];
      //if(j + 'A' == 'A' || j + 'A' == 'C' || j + 'A' == 'G' || j + 'A' == 'T') {
        //cout << j << ' ' << g[i][j] << ' ' << dp[g[i][j]] << '\n';
      //}
      if(dp[g[i][j]] < dp[i] && (j + 'A' == 'A' || j + 'A' == 'C' || j + 'A' == 'G' || j + 'A' == 'T')) {
        zy[i] = j;
        dp[i] = dp[g[i][j]];
      }
    }
    dp[i]++;
    //cout << i << ',' << dp[i] << ',' << zy[i] << '\n';
    //cout << '\n';
    if(i) {
      nxt[s[i] - 'A'] = i;
    }
  }
  //cout << '\n';
  for(int i = 0; i != n + 1; i = g[i][zy[i]]) {
    cout << char(zy[i] + 'A');
  }
  cout << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

::::

::::info[CodeForces346B Lucky Common Subsequence]{open} 给你三个字符串 s_1, s_2, s_3，求最长的是 s_1 和 s_2 的公共子序列且不是 s_3 的子串的字符串的长度。 ::::

从这里开始，事情变得综合运用起来。

考虑对 s_1 和 s_2 建子序列自动机，对 s_3 建 KMP 自动机，然后设 dp_{i_1, i_2, i_3} 为当前第 j 个字符串在第 i_j 个位置的方案数，做就可以了，没有太大的难度。

::::success[Code]

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

int n, m, o, f[110][30], g[110][30], fail[110], h[110][30], nxt[30], dp[110][110][110], zy[110][110][110];
string s1, s2, vi;

int DFS(int q1, int q2, int q3) {
  if(q1 == n + 1 || q2 == m + 1) {
    return 0;
  }
  if(dp[q1][q2][q3]) {
    return dp[q1][q2][q3];
  }
  for(int i = 0; i < 26; i++) {
    if(h[q3][i] != o) {
      if(DFS(f[q1][i], g[q2][i], h[q3][i]) > dp[q1][q2][q3]) {
        dp[q1][q2][q3] = DFS(f[q1][i], g[q2][i], h[q3][i]);
        zy[q1][q2][q3] = i;
      }
    }
  }
  dp[q1][q2][q3]++;
  return dp[q1][q2][q3];
}

void gans(int q1, int q2, int q3) {
  int tmp = zy[q1][q2][q3];
  if(f[q1][tmp] != n + 1 && g[q2][tmp] != m + 1) {
    cout << char(tmp + 'A');
    gans(f[q1][tmp], g[q2][tmp], h[q3][tmp]);
  }
}

int main() {
  cin >> s1 >> s2 >> vi;
  n = s1.size(), m = s2.size(), o = vi.size();
  s1 = ' ' + s1, s2 = ' ' + s2, vi = ' ' + vi;
  h[0][vi[1] - 'A'] = 1;
  //cout << h[0][0] << '\n';
  for(int i = 1; i <= o; i++) {
    for(int j = 0; j < 26; j++) {
      if(i < o && vi[i + 1] - 'A' == j) {
        h[i][j] = i + 1;
        fail[i + 1] = h[fail[i]][j];
      }else {
        h[i][j] = h[fail[i]][j];
      }
      //cout << h[i][j] << ' ';
    }
    //cout << '\n';
  }
  fill(nxt, nxt + 26, n + 1);
  for(int i = n; i >= 0; i--) {
    for(int j = 0; j < 26; j++) {
      f[i][j] = nxt[j];
    }
    if(i) {
      nxt[s1[i] - 'A'] = i;
    }
  }
  fill(nxt, nxt + 26, m + 1);
  for(int i = m; i >= 0; i--) {
    for(int j = 0; j < 26; j++) {
      g[i][j] = nxt[j];
    }
    if(i) {
      nxt[s2[i] - 'A'] = i;
    }
  }
  //cout << DFS(0, 0, 0) << '\n';
  if(!(DFS(0, 0, 0) - 1)) {
    cout << 0 << '\n';
    return 0;
  }
  gans(0, 0, 0);
  cout << '\n';
  return 0;
}

::::

::::info[P4608 所有公共子序列问题]{open} 求两个字符串所有的不同公共子序列。 ::::

对于 k = 1 的情况可以搜索，对于 k = 0 的情况可以 dp，思维难度几乎为 0，但是实现吗……

我在这里列举所有的细节：

• 内存动态开，否则可能导致 MLE
• 需要压位高精度

虽然看似只有两个，但是能够带来的效果是逆天的。

这里放置代码以供参考，时间复杂度……O(\text{能过})，毕竟这是 FJOI。

::::success[Code...]{open}

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

const int kB = 1e9;

struct node {
  vector<int> num;
  int len;

  node& operator =(int b) {
    num.clear();
    num.push_back(b % kB);
    if(b >= kB) {
      num.push_back(b / kB);
    }
    len = num.size();
    return *this;
  }
  node& operator =(node b) {
    num = b.num;
    len = b.len;
    return *this;
  }

  node operator +(node b) {
    node c;
    c.num.clear();
    c.len = max(len, b.len) + 1;
    c.num.resize(c.len);
    for(int i = 0; i < c.len; i++) {
      c.num[i] = (i >= len? 0 : num[i]) + (i >= b.len? 0 : b.num[i]);
    }
    for(int i = 0; i < c.len; i++) {
      if(c.num[i] >= kB) {
        c.num[i + 1]++;
        c.num[i] -= kB;
      }
    }
    if(!c.num[c.len - 1]) {
      c.num.pop_back();
      c.len--;
    }
    return c;
  }
  node& operator +=(node b) {
    return (*this) = operator+(b);
  }
  void print(ostream &os) {
    for(int i = len - 1; i >= 0; i--) {
      if(i != len - 1) {
        if(num[i] < 100000000) {
          os << 0;
        }
        if(num[i] < 10000000) {
          os << 0;
        }
        if(num[i] < 1000000) {
          os << 0;
        }
        if(num[i] < 100000) {
          os << 0;
        }
        if(num[i] < 10000) {
          os << 0;
        }
        if(num[i] < 1000) {
          os << 0;
        }
        if(num[i] < 100) {
          os << 0;
        }
        if(num[i] < 10) {
          os << 0;
        }
      }
      os << num[i];
    }
  }
};

int n, m, f[3030][60], g[3030][60], k, nxt[60], ans;
string s, t, tmp;
map<pair<int, int>, node> dp;

int trans(char x) {
  return (x >= 'a'? x - 'a' + 26 : x - 'A');
}

char anti(int x) {
  return (x >= 26? x - 26 + 'a' : x + 'A');
}

void DFS(int q1, int q2) {
  if(q1 == n + 1 || q2 == m + 1) {
    return ;
  }
  cout << tmp << '\n';
  ans++;
  for(int i = 0; i < 52; i++) {
    tmp += anti(i);
    DFS(f[q1][i], g[q2][i]);
    tmp.pop_back();
  }
}

void DP(int q1, int q2) {
  if(dp.count({q1, q2})) {
    return ;
  }
  dp[{q1, q2}] = 1;
  for(int i = 0; i < 52; i++) {
    if(f[q1][i] != n + 1 && g[q2][i] != m + 1) {
      //cout << q1 << ' ' << q2 << ' ' << f[q1][i] << ' ' << g[q2][i] << '\n';
      DP(f[q1][i], g[q2][i]);
      dp[{q1, q2}] += dp[{f[q1][i], g[q2][i]}];
    }
  }
  //cout << q1 << ' ' << q2 << ' ';
  //dp[{q1, q2}].print(cout);
  //cout << '\n';
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  cin >> s >> t;
  cin >> k;
  s = ' ' + s;
  t = ' ' + t;
  fill(nxt, nxt + 52, n + 1);
  for(int i = n; i >= 0; i--) {
    for(int j = 0; j < 52; j++) {
      f[i][j] = nxt[j];
    }
    if(i) {
      nxt[trans(s[i])] = i;
    }
  }
  fill(nxt, nxt + 52, m + 1);
  for(int i = m; i >= 0; i--) {
    for(int j = 0; j < 52; j++) {
      g[i][j] = nxt[j];
    }
    if(i) {
      nxt[trans(t[i])] = i;
    }
  }
  if(k) {
    DFS(0, 0);
    cout << ans << '\n';
  }else {
    DP(0, 0);
    dp[{0, 0}].print(cout);
  }
  return 0;
}

::::

AC 自动机

::::info[P3808 AC 自动机 I]{open} 给定 n 个模式串 s_i 和一个文本串 t，求有多少个不同的模式串在文本串里出现过。
两个模式串不同当且仅当他们 编号 不同。 ::::

Trie 能做多模式前缀匹配，但是这玩意是子串匹配；

KMP 能做单模式子串匹配，但是这玩意是多模式的。

咦？这俩的功能好像可以互补？

我们不妨把他们结合起来，把 trans 和 fail 的思想放到字典树上，这样我们就可以在字典树上舍弃前缀了。而，前缀，再舍弃一个前缀，不就是子串吗？于是，对于某一个点，它每一次跳 fail，跳到的所有点都会对应一个子串。

于是我们按照 BFS 序，使用与 KMP 自动机 完全一样 的方式处理，就可以建出来了。

注意到暴力跳 fail 有 100% 的概率超时。AC 自动机的码量应该是所有算法里面最为大的几个，因为它的码量大概是 Trie 与 KMP 自动机的码量之和。

::::success[Code]

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

struct trie {
  int ch[1000010][26], cnt = 0, num[1000010], nxt[1000010][26], fail[1000010], vis[1000010];

  void init() {
    memset(ch, -1, sizeof(ch));
  }

  void insert(const string &s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'a'] == -1) {
        ch[u][i - 'a'] = ++cnt;
      }
      u = ch[u][i - 'a'];
    }
    num[u]++;
  }

  void build() {
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) {
        nxt[0][i] = ch[0][i];
        q.push(ch[0][i]);
      }
    }
    for(; q.size(); q.pop()) {
      int tmp = q.front();
      for(int i = 0; i < 26; i++) {
        if(ch[tmp][i] != -1) {
          nxt[tmp][i] = ch[tmp][i];
          fail[ch[tmp][i]] = nxt[fail[tmp]][i];
          q.push(ch[tmp][i]);
        }else {
          nxt[tmp][i] = nxt[fail[tmp]][i];
        }
      }
    }
  }

  int query(const string &s) {
    int u = 0, ans = 0;
    for(auto i : s) {
      u = nxt[u][i - 'a'];
      if(num[u] && !vis[u]) {
        for(int j = u; !vis[j]; j = fail[j]) {
          ans += num[j], vis[j] = 1;
        }
      }
    }
    return ans;
  }
}tr;

int n;
string s[1000010], t;

signed main() {
  tr.init();
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    tr.insert(s[i]);
  }
  tr.build();
  cin >> t;
  cout << tr.query(t) << '\n';
  return 0;
}

::::

::::info[P3796 AC 自动机 II]{open} 有 N 个由小写字母组成的模式串以及一个文本串 T。每个模式串可能会在文本串中出现多次。你需要找出 哪些 模式串在文本串 T 中出现的次数最多。 ::::

直接做匹配就可以了，但是注意这次是子树求和，而且可能有两个模式串 完全一样。

::::success[Code]

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

struct trie {
  int ch[20020][26], cnt, num[20020], occ[20020], nxt[20020][26], fail[20020], val[20020], mx;

  trie() : ch(), cnt(0), num(), occ(), nxt(), fail(), val(), mx(0) {
    memset(ch, -1, sizeof(ch));
    memset(num, 0, sizeof(num));
    memset(occ, 0, sizeof(occ));
    memset(nxt, 0, sizeof(nxt));
    memset(fail, 0, sizeof(fail));
    memset(val, 0, sizeof(val));
  }

  void init() {
    for(int i = 0; i <= cnt; i++) {
      for(int j = 0; j < 26; j++) {
        ch[i][j] = -1, nxt[i][j] = 0;
      }
      num[i] = fail[i] = val[i] = occ[i] = 0;
    }
    cnt = 0, mx = 0;
  }

  void insert(const string &s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'a'] == -1) {
        ch[u][i - 'a'] = ++cnt;
      }
      u = ch[u][i - 'a'];
    }
    num[u]++;
  }

  int get(const string &s) {
    int u = 0;
    for(auto i : s) {
      u = ch[u][i - 'a'];
    }
    return u;
  }

  void build() {
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) {
        nxt[0][i] = ch[0][i];
        q.push(ch[0][i]);
      }
    }
    for(; q.size(); q.pop()) {
      int tmp = q.front();
      for(int i = 0; i < 26; i++) {
        if(ch[tmp][i] != -1) {
          nxt[tmp][i] = ch[tmp][i];
          fail[ch[tmp][i]] = nxt[fail[tmp]][i];
          q.push(ch[tmp][i]);
        }else {
          nxt[tmp][i] = nxt[fail[tmp]][i];
        }
      }
    }
  }

  void query(const string &s) {
    int u = 0;
    for(auto i : s) {
      u = nxt[u][i - 'a'];
      for(int j = u; j; j = fail[j]) {
        occ[j]++;
      }
    }
    for(int i = 0; i <= cnt; i++) {
      if(num[i]) {
        mx = max(mx, occ[i]);
      }
    }
  }
}tr;

int n;
string s[220], t;
vector<string> v;

void solve() {
  tr.init();
  v.clear();
  for(int i = 1; i <= n; i++) {
    cin >> s[i];
    tr.insert(s[i]);
  }
  tr.build();
  cin >> t;
  tr.query(t);
  for(int i = 1; i <= n; i++) {
    int tmp = tr.get(s[i]);
    if(tr.occ[tmp] == tr.mx) {
      v.push_back(s[i]);
    }
  }
  cout << tr.mx << '\n';
  for(auto i : v) {
    cout << i << '\n';
  }
}

signed main() {
  for(cin >> n; n; cin >> n) {
    solve();
  }
  return 0;
}

::::

::::info[P5357 【模板】AC 自动机]{open} 给你一个文本串 S 和 n 个模式串 T_{1 \sim n}，请你分别求出每个模式串 T_i 在 S 中出现的次数。 ::::

与上面那个题一模一样。直接做就可以了。

::::success[Code]

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

/*
const int kSL = 1000000;

struct AC {
  int ch[kSL + 10][26], fail[kSL + 10], trans[kSL + 10][26], occ[kSL], cnt;
  vector<int> ord;

  AC() : ch(), fail(), trans(), occ(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
    memset(occ, -1, sizeof(occ));
  }

  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'a'] == -1) ch[u][i - 'a'] = ++cnt;
      u = ch[u][i - 'a'];
    }
    occ[u] = 1;
  }

  void build() {
    ord = {0};
    fail[0] = 0;
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) trans[0][i] = ch[0][i], fail[ch[0][i]] = 0, q.push(ch[0][i]);
    }
    for(; q.size(); q.pop()) {
      int u = q.front();
      ord.push_back(u);
      for(int i = 0; i < 26; i++) {
        if(ch[u][i] == -1) trans[u][i] = trans[fail[u]][i];
        else trans[u][i] = ch[u][i], fail[trans[u][i]] = trans[fail[u]][i], q.push(ch[u][i]);
      }
    }
  }

  void match(string s) {
    int u = 0;
    for(auto i : s) {
      u = trans[u][i - 'a'];
    }
  }
}tr;
*/

const int kSL = 1000000;

int ans[200020];

struct AC {
  int ch[kSL + 10][26], fail[kSL + 10], trans[kSL + 10][26], occ[kSL], cnt, val[kSL];
  vector<int> ord, idx[kSL];

  AC() : ch(), fail(), trans(), occ(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
    memset(occ, -1, sizeof(occ));
  }

  void insert(string s, int x) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'a'] == -1) ch[u][i - 'a'] = ++cnt;
      u = ch[u][i - 'a'];
    }
    occ[u] = 1, idx[u].push_back(x);
  }

  void build() {
    ord = {0};
    fail[0] = 0;
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) trans[0][i] = ch[0][i], fail[ch[0][i]] = 0, q.push(ch[0][i]);
      else trans[0][i] = 0;
    }
    //cout << 0 << ' ' << trans[0][0] << ' ' << 'a' << '\n';
    //cout << 0 << ' ' << trans[0][1] << ' ' << 'b' << '\n';
    for(; q.size(); q.pop()) {
      int u = q.front();
      ord.push_back(u);
      for(int i = 0; i < 26; i++) {
        if(ch[u][i] == -1) trans[u][i] = trans[fail[u]][i];
        else trans[u][i] = ch[u][i], fail[trans[u][i]] = trans[fail[u]][i], q.push(ch[u][i]);
      }
      //cout << u << ' ' << trans[u][0] << ' ' << 'a' << '\n';
      //cout << u << ' ' << trans[u][1] << ' ' << 'b' << '\n';
    }
  }

  void match(string s) {
    int u = 0;
    for(auto i : s) {
      u = trans[u][i - 'a'];
      val[u]++;
    }
    for(int i = ord.size() - 1; i >= 0; i--) {
      if(ord[i]) val[fail[ord[i]]] += val[ord[i]];
      for(auto j : idx[ord[i]]) ans[j] = val[ord[i]];
    }
  }
}tr;

int n;
string s;

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> s;
    tr.insert(s, i);
  }
  tr.build();
  cin >> s;
  tr.match(s);
  for(int i = 1; i <= n; i++) cout << ans[i] << '\n';
  return 0;
}

::::

::::info[P14363 [CSP-S 2025] 谐音替换]{open} 有 n 对等长的字符串 (x_i, y_i)，现在给你 m 组询问，每一组询问给定字符串 a 和 b，你可以选择一个 i 然后把某一个 a 中的 x_i 替换为 y_i。求把 a 变成 b 的方案数。保证 a = b，但是不保证二者等长。 ::::

场上思路。

首先考虑到子串匹配就会想到 AC 自动机，然后就要尝试把 x_i 和 y_i 对齐。卡死，不知道怎么对齐。

场下思路。

考虑直接把 (x_i, y_i) 中，二者不同的部分提取出来（即设 x_i = s_1 + a + s_2，y_i = s_1 + b + s_2），然后把这个二元组变换为 s_1 + \# + a + b + \# + s_2，其中 \# 为某一个特殊字符。

把 a 和 b 也这样变换，然后你就会发现特殊字符帮助你对齐了位置。然后直接多模式匹配即可。注意到 a 和 b 可能不等长。

::::success[Code]

#include <bits/stdc++.h>
//#define int longlong
#define popc __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
using longlong = long long;

int ttt(char x) {
  if(x == '#') return 26;
  return x - 'a';
}

// kSL adjusts length, kSigma adjusts character set size.
const int kSL = 5000000, kSigma = 27;

// You can also add features yourself.
struct AC {
  // ch is child in trie, fail is failure pointer, trans is transition edge, occ is occurence, cnt is node count, ord is the BFS order.
  int ch[kSL + 10][kSigma], fail[kSL + 10], trans[kSL + 10][kSigma], occ[kSL], cnt, fs[kSL];
  vector<int> ord;

  // RAII(I curse all those people who don't use RAII with a 100% chance of not initializing something)
  AC() : ch(), fail(), trans(), occ(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
  }

  // insert an string. DISCLAIMER: if the last called function is insert(), don't call match() or the program may have unexpected behavior
  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][ttt(i)] == -1) ch[u][ttt(i)] = ++cnt;
      u = ch[u][ttt(i)];
    }
    occ[u]++;
  }

  void build() {
    ord = {0};
    fail[0] = 0;
    queue<int> q;
    for(int i = 0; i < kSigma; i++) {
      if(ch[0][i] != -1) trans[0][i] = ch[0][i], fail[ch[0][i]] = 0, q.push(ch[0][i]);
      else trans[0][i] = 0;
    }
    for(; q.size(); q.pop()) {
      int u = q.front();
      ord.push_back(u);
      for(int i = 0; i < kSigma; i++) {
        if(ch[u][i] == -1) trans[u][i] = trans[fail[u]][i];
        else trans[u][i] = ch[u][i], fail[ch[u][i]] = trans[fail[u]][i], q.push(ch[u][i]);
      }
    }
    for(auto u : ord) fs[u] = fs[fail[u]] + occ[u];
  }

  int match(string s) {
    int u = 0, ans = 0;
    for(auto i : s) {
      u = trans[u][ttt(i)];
      //cout << u << ' ' << fs[u] << '\n';
      ans += fs[u];
    }
    return ans;
  }
}tr;

int n, q;
string s1, s2;

string trans(string &x, string &y) {
  int cl = 0, cr = x.size() - 1;
  for(; x[cl] == y[cl]; cl++);
  for(; x[cr] == y[cr]; cr--);
  return x.substr(0, cl) + '#' + x.substr(cl, cr - cl + 1) + y.substr(cl, cr - cl + 1) + '#' + x.substr(cr + 1);
}

signed main() {
  cin >> n >> q;
  for(; n--; ) {
    cin >> s1 >> s2;
    if(s1 == s2) continue;
    tr.insert(trans(s1, s2));
  }
  tr.build();
  for(; q--; ) {
    cin >> s1 >> s2;
    if(s1.size() != s2.size()) {
      cout << 0 << '\n';
      continue;
    }
    //cout << trans(s1, s2) << '\n';
    cout << tr.match(trans(s1, s2)) << '\n';
  }
  return 0;
}

::::

::::info[P2444 [POI 2000] 病毒]{open} 给你 n 个模式串，判断是否有一个文本串不包含这些模式串的任何一个作为子串。 ::::

考虑把这个文本串直接扔到模式串组成的 AC 自动机上开始匹配。如果匹配到一个跳 fail 能够跳到某一个模式串的节点就死了。

所以我们发现，只要可以找出一个不经过任何会死掉的节点的环，我们就可以在环上 孤独的 转个不停。所以 AC 自动机上找环即可。

::::success[Code]

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

struct AC {
  int cnt, ch[30030][2], fail[30030], trans[30030][2], ina[30030], vis[30030];

  AC() : cnt(0), ch(), fail(), trans() {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
  }

  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      int x = i - '0';
      if(ch[u][x] == -1) ch[u][x] = ++cnt;
      u = ch[u][x];
    }
    ina[u] = 1;
  }

  void build() {
    queue<int> q;
    fail[0] = 0;
    trans[0][0] = trans[0][1] = 0;
    if(ch[0][0] != -1) q.push(ch[0][0]), fail[ch[0][0]] = 0, trans[0][0] = ch[0][0];
    if(ch[0][1] != -1) q.push(ch[0][1]), fail[ch[0][1]] = 0, trans[0][1] = ch[0][1];
    for(; q.size(); q.pop()) {
      int tmp = q.front();
      if(ch[tmp][0] != -1) q.push(ch[tmp][0]), fail[ch[tmp][0]] = trans[fail[tmp]][0], trans[tmp][0] = ch[tmp][0];
      else trans[tmp][0] = trans[fail[tmp]][0];
      if(ch[tmp][1] != -1) q.push(ch[tmp][1]), fail[ch[tmp][1]] = trans[fail[tmp]][1], trans[tmp][1] = ch[tmp][1];
      else trans[tmp][1] = trans[fail[tmp]][1];
      if(ina[fail[tmp]]) ina[tmp] = 1;
    }
    //for(int i = 0; i <= 7; i++) cout << fail[i] << ' ';
    //cout << '\n';
    //for(int i = 0; i <= 7; i++) cout << ina[i] << ' ';
    //cout << '\n';
    //for(int i = 0; i <= 7; i++) cout << trans[i][0] << ',' << trans[i][1] << ' ';
    //cout << '\n';
  }
  bool gans(int x) {
    if(ina[x]) return 0;
    if(vis[x]) return (vis[x] == 1);
    vis[x] = 1;
    bool f = gans(trans[x][0]) || gans(trans[x][1]);
    vis[x] = -1;
    return f;
  }
}trie;

int n;
string s;

int main() {
  cin >> n;
  for(int i = 1; i <= n; i++) {
    cin >> s;
    trie.insert(s);
  }
  trie.build();
  cout << (trie.gans(0)? "TAK" : "NIE") << '\n';
  return 0;
}
/*
3
00
11
0100
*/

::::

::::info[P3121 [USACO15FEB] Censoring G]{open} FJ 把杂志上所有的文章摘抄了下来并把它变成了一个长度不超过 10^5 的字符串 s。他有一个包含 n 个单词的列表，列表里的 n 个单词记为 t_1 \cdots t_n。他希望从 s 中删除这些单词。

FJ 每次在 s 中找到最早出现的列表中的单词（最早出现指该单词的开始位置最小），然后从 s 中删除这个单词。他重复这个操作直到 s 中没有列表里的单词为止。注意删除一个单词后可能会导致 s 中出现另一个列表中的单词。

FJ 注意到列表中的单词不会出现一个单词是另一个单词子串的情况，这意味着每个列表中的单词在 s 中出现的开始位置是互不相同的。

请帮助 FJ 完成这些操作并输出最后的 s。 ::::

直接把违禁词扔到 AC 自动机上然后模拟题意即可。并不综合。

::::success[Code]

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

struct trie {
  int ch[100010][26], trans[100010][26], val[100010], fail[100010], cnt;

  trie() : ch(), trans(), fail(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(trans, -1, sizeof(trans));
    memset(fail, -1, sizeof(fail));
  }

  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'a'] == -1) ch[u][i - 'a'] = ++cnt;
      u = ch[u][i - 'a'];
    }
    val[u] = s.size();
  }

  void build() {
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) q.push(ch[0][i]), trans[0][i] = ch[0][i], fail[ch[0][i]] = 0;
      else trans[0][i] = 0;
    }
    for(; q.size(); ) {
      int tmp = q.front();
      q.pop();
      for(int i = 0; i < 26; i++) {
        if(ch[tmp][i] != -1) trans[tmp][i] = ch[tmp][i], fail[ch[tmp][i]] = trans[fail[tmp]][i], q.push(ch[tmp][i]);
        else trans[tmp][i] = trans[fail[tmp]][i];
      }
      val[tmp] |= val[fail[tmp]];
    }
  }
}tr;

int n;
string s, t;
vector<pair<char, int> > v;

int main() {
  for(cin >> s >> n; n--; ) {
    cin >> t;
    tr.insert(t);
  }
  tr.build();
  v.push_back({'#', 0});
  for(int i = 0; i < s.size(); i++) {
    v.push_back({s[i], tr.trans[v.back().second][s[i] - 'a']});
    int tmp = tr.val[v.back().second];
    for(; tmp--; v.pop_back());
  }
  for(auto i : v) if(i.first != '#') cout << i.first;
  cout << '\n';
  return 0;
}

::::

::::info[P3041 [USACO12JAN] Video Game G]{open} 有 3 种字符和一个长度为 k 的文本串。还有 n 个模式串。现在，如果你能任意操控长度为 k 的文本串，求所有模式串在文本串中出现的次数之和的最大值。 ::::

设 dp_{l, i} 为当前在 AC 自动机的节点 i，并且已经用掉了 l 个字符的答案。容易得到 dp_{l, i} + occ_{trans_{i, c}} \to dp_{l + 1, trans_{i, c}}，初始 dp_{0, 0} = 0。直接 dp 即可。

::::success[Code]

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

struct trie {
  int ch[330][26], trans[330][26], val[330], fail[330], dp[1010][330], cnt;

  trie() : ch(), trans(), fail(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(trans, -1, sizeof(trans));
    memset(fail, -1, sizeof(fail));
    memset(dp, 0x80, sizeof(dp));
    dp[0][0] = 0;
  }

  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][i - 'A'] == -1) ch[u][i - 'A'] = ++cnt;
      u = ch[u][i - 'A'];
    }
    val[u]++;
  }

  void build() {
    queue<int> q;
    for(int i = 0; i < 26; i++) {
      if(ch[0][i] != -1) q.push(ch[0][i]), trans[0][i] = ch[0][i], fail[ch[0][i]] = 0;
      else trans[0][i] = 0;
    }
    for(; q.size(); ) {
      int tmp = q.front();
      q.pop();
      for(int i = 0; i < 26; i++) {
        if(ch[tmp][i] != -1) trans[tmp][i] = ch[tmp][i], fail[ch[tmp][i]] = trans[fail[tmp]][i], q.push(ch[tmp][i]);
        else trans[tmp][i] = trans[fail[tmp]][i];
      }
      val[tmp] += val[fail[tmp]];
    }
    for(int i = 0; i < 1000; i++) {
      for(int j = 0; j <= cnt; j++) {
        for(int x = 0; x < 26; x++) {
          dp[i + 1][trans[j][x]] = max(dp[i + 1][trans[j][x]], dp[i][j] + val[trans[j][x]]);
        }
      }
    }
  }

  int get(int x) {
    int ans = 0;
    for(int i = 0; i <= cnt; i++) ans = max(ans, dp[x][i]);
    return ans;
  }
}tr;

int n, k;
string s;

int main() {
  for(cin >> n >> k; n--; ) {
    cin >> s;
    tr.insert(s);
  }
  tr.build();
  cout << tr.get(k) << '\n';
  return 0;
}

::::

::::info[P3311 [SDOI2014] 数数]{open} 我们称一个正整数 x 是幸运数，当且仅当它的十进制表示中不包含数字串集合 s 中任意一个元素作为其子串。例如当 s = \{22, 333, 0233\} 时，233 是幸运数，2333、20233、3223 不是幸运数。给定 n 和 s，计算不大于 n 的幸运数个数。

答案对 10^9 + 7 取模。 ::::

考虑 dp，设 dp_{i, x, 1/2} 为目前匹配到了第 i 位且当前在节点 x，有/无 n 的限制的方案数。转移与之前的大差不差。但是，等等，s 中的元素可能有前导 0，但是 x 没有啊！所以，设 dp_{i, x, j=0/1/2} 为目前匹配到了第 i 位且当前在节点 x，并且：

然后可以直接转移。注意如果不是第一位就开始匹配，dp_{i, x, 0} 会直接转移到 dp_{i', x', 2}。

::::success[Code]

#include <bits/stdc++.h>
#define int longlong
#define popc __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
using longlong = long long;

int ttt(char x) {
  return x - '0';
}

// kSL adjusts length, kSigma adjusts character set size.
const int kSL = 1500, kSigma = 10, kMod = 1000000007;

// You can also add features yourself.
struct AC {
  // ch is child in trie, fail is failure pointer, trans is transition edge, occ is occurence, cnt is node count, ord is the BFS order.
  int ch[kSL + 10][kSigma], fail[kSL + 10], trans[kSL + 10][kSigma], occ[kSL], cnt, fs[kSL];
  vector<int> ord;

  // RAII(I curse all those people who don't use RAII with a 100% chance of not initializing something)
  AC() : ch(), fail(), trans(), occ(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
  }

  // insert an string. DISCLAIMER: if the last called function is insert(), don't call match() or the program may have unexpected behavior
  void insert(string s) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][ttt(i)] == -1) ch[u][ttt(i)] = ++cnt;
      u = ch[u][ttt(i)];
    }
    occ[u] = 1;
  }

  void build() {
    ord = {0};
    fail[0] = 0;
    queue<int> q;
    for(int i = 0; i < kSigma; i++) {
      if(ch[0][i] != -1) trans[0][i] = ch[0][i], fail[ch[0][i]] = 0, q.push(ch[0][i]);
      else trans[0][i] = 0;
    }
    for(; q.size(); q.pop()) {
      int u = q.front();
      occ[u] |= occ[fail[u]];
      ord.push_back(u);
      for(int i = 0; i < kSigma; i++) {
        if(ch[u][i] == -1) trans[u][i] = trans[fail[u]][i];
        else trans[u][i] = ch[u][i], fail[ch[u][i]] = trans[fail[u]][i], q.push(ch[u][i]);
      }
    }
  }
}tr;

string n, x;
int l, dp[1212][1515][3];

signed main() {
  for(cin >> n >> l; l--; ) {
    cin >> x;
    tr.insert(x);
  }
  l = n.size();
  tr.build();
  dp[0][0][0] = 1;
  //cout << tr.trans[0][1] << ' ' << tr.trans[0][2] << '\n';
  for(int i = 0; i < l; i++) {
    for(int j = 0; j <= tr.cnt; j++) {
      if(!tr.occ[j]) {
        for(int k = 0; k < kSigma; k++) {
          int zrr = tr.trans[j][k];
          if(!tr.occ[zrr]) {
            if(!k) dp[i + 1][j][0] = (dp[i + 1][j][0] + dp[i][j][0]) % kMod;
            if(k && k == ttt(n[i]) && !i) dp[i + 1][zrr][1] = (dp[i + 1][zrr][1] + dp[i][j][0]) % kMod;
            if(k && (k < ttt(n[i]) || i)) dp[i + 1][zrr][2] = (dp[i + 1][zrr][2] + dp[i][j][0]) % kMod;

            if(k == ttt(n[i])) dp[i + 1][zrr][1] = (dp[i + 1][zrr][1] + dp[i][j][1]) % kMod;
            if(k < ttt(n[i])) dp[i + 1][zrr][2] = (dp[i + 1][zrr][2] + dp[i][j][1]) % kMod;

            dp[i + 1][zrr][2] = (dp[i + 1][zrr][2] + dp[i][j][2]) % kMod;
          }
        }
      }
      //cout << (dp[i][j][0] + dp[i][j][1] + dp[i][j][2]) % kMod << ' ';
    }
    //cout << '\n';
  }
  int ans = 0;
  for(int j = 0; j <= tr.cnt; j++) {
    //cout << (dp[l][j][0] + dp[l][j][1] + dp[l][j][2]) % kMod << ' ';
    ans = (ans + dp[l][j][1] + dp[l][j][2]) % kMod;
  }
  cout << ans << '\n';
  return 0;
}

::::

::::info[P6125 [JSOI2009] 有趣的游戏]{open} 有 n 个模式串和 m 种字符，保证模式串里面只有这 m 种字符。现在有一个无限长的文本串，文本串的每一个字符相互独立且在 m 种字符中随机，随机到第 i 种字符的概率是 pr_i。这样，存在一个最小的 i 使得某一个模式串是从 i 开始的文本串的前缀。现在求第 x 个模式串最先出现的概率。 ::::

考虑 dp_i 为最后停留在 i 的概率。易得 dp_i = \sum \limits_{trans_{j, c} = i, j \text{不是叶子}} pr_c dp_j + [i = 0]。那这个玩意肯定一堆环，不过这些东西都是线性的，所以可以列出一个线性方程组，然后高斯消元即可。不会高斯消元出门左转。

其实一开始我准备使用人类智慧模拟一个很长的长度，但是发现收敛速度比较慢，然后就废弃了。

::::success[Code]

#include <bits/stdc++.h>
#define int longlong
#define ldouble long double
#define popc __builtin_popcount
#define ctz __builtin_ctz
using namespace std;
using longlong = long long;

struct linear {

  const ldouble eps = 1e-17;

  int n, nt;
  ldouble arr[110][110];

  int check(int x) {
    for(int i = 0; i <= n; i++) {
      if(arr[x][i] >= eps || arr[x][i] <= -eps) return 0;
    }
    return (arr[x][n + 1] >= eps || arr[x][n + 1] <= -eps? 1 : 2);
  }

  int gauss() {
    for(int i = 0; i <= n; i++) {
      bool f = 1;
      if(arr[i][i] < eps && arr[i][i] > -eps) {
        f = 0;
        for(int j = 0; j <= n; j++) {
          if(arr[j][i] >= eps || arr[j][i] <= -eps) {
            bool f1 = 1;
            for(int k = 0; k < i; k++) {
              if(arr[j][k]) f1 = 0;
            }
            if(!f1) continue;
            for(int k = 0; k <= n + 1; k++) arr[i][k] += arr[j][k];
            f = 1;
            break;
          }
        }
        if(!f) {
          nt = 1;
          continue;
        }
      }
      for(int j = 0; j <= n; j++) {
        if(j == i) continue;
        ldouble tmp = arr[j][i] / arr[i][i];
        for(int k = 0; k <= n + 1; k++) arr[j][k] -= arr[i][k] * tmp;
      }
    }
    for(int i = 0; i <= n; i++) {
      int tmp = check(i);
      if(tmp == 1) return -1;
      if(tmp == 2) nt = 1;
    }
    if(nt) return 0;
    for(int i = 0; i <= n; i++) {
      arr[i][n + 1] /= arr[i][i];
      arr[i][i] = 1;
    }
    return 1;
  }
}gauss;

int ttt(char x) {
  return x - 'A';
}

// kSL adjusts length, kSigma adjusts character set size.
const int kSL = 1500, kSigma = 10, kMod = 1000000007;

// You can also add features yourself.
struct AC {
  // ch is child in trie, fail is failure pointer, trans is transition edge, occ is occurence, cnt is node count, ord is the BFS order.
  int ch[kSL + 10][kSigma], fail[kSL + 10], trans[kSL + 10][kSigma], occ[kSL], cnt, fs[kSL];
  vector<int> ord;

  // RAII(I curse all those people who don't use RAII with a 100% chance of not initializing something)
  AC() : ch(), fail(), trans(), occ(), cnt(0) {
    memset(ch, -1, sizeof(ch));
    memset(fail, -1, sizeof(fail));
    memset(trans, -1, sizeof(trans));
  }

  // insert an string. DISCLAIMER: if the last called function is insert(), don't call match() or the program may have unexpected behavior
  void insert(string s, int x) {
    int u = 0;
    for(auto i : s) {
      if(ch[u][ttt(i)] == -1) ch[u][ttt(i)] = ++cnt;
      u = ch[u][ttt(i)];
    }
    occ[u] = x;
  }

  void build() {
    ord = {0};
    fail[0] = 0;
    queue<int> q;
    for(int i = 0; i < kSigma; i++) {
      if(ch[0][i] != -1) trans[0][i] = ch[0][i], fail[ch[0][i]] = 0, q.push(ch[0][i]);
      else trans[0][i] = 0;
    }
    for(; q.size(); q.pop()) {
      int u = q.front();
      ord.push_back(u);
      for(int i = 0; i < kSigma; i++) {
        if(ch[u][i] == -1) trans[u][i] = trans[fail[u]][i];
        else trans[u][i] = ch[u][i], fail[ch[u][i]] = trans[fail[u]][i], q.push(ch[u][i]);
      }
    }
  }
}tr;

int n, l, m, p, q;
double prob[11], ans[11];
string s;

signed main() {
  cin >> n >> l >> m;
  for(int i = 0; i < m; i++) {
    cin >> p >> q;
    prob[i] = 1.0 * p / q;
  }
  for(int i = 1; i <= n; i++) {
    cin >> s;
    tr.insert(s, i);
  }
  tr.build();
  gauss.n = tr.cnt;
  for(int i = 0; i <= tr.cnt; i++) {
    gauss.arr[i][i] = 1;
    if(!tr.occ[i]) {
      for(int j = 0; j < m; j++) {
        gauss.arr[tr.trans[i][j]][i] -= prob[j];
      }
    }
  }
  gauss.arr[0][gauss.n + 1] = 1;
  gauss.gauss();
  for(int i = 0; i <= tr.cnt; i++) {
    ans[tr.occ[i]] = gauss.arr[i][gauss.n + 1];
  }
  for(int i = 1; i <= n; i++) {
    cout << fixed << setprecision(2) << ans[i] << '\n';
  }
  return 0;
}

::::