字符串 cpp 模板

本篇内容为 oi-wiki 字符串篇 的学习笔记

以 代码更新汇总 中的代码为主。

字典树（Trie）

假设在一堆仅有大/小写字母的字符串中，需要快速检测某个字符串是否存在，那么 Trie 是个不错的选择。

仅包含小写字母的 Trie（大写字母同理）

class Trie {
  using Node = std::array<int, 26>;
  std::vector<Node> nxt;
  // 0 表示没有，1 表示有且没被访问过，2 表示有且被访问过
  std::vector<int> tag;
  void addNode(int fa, int c) {
    nxt[fa][c] = nxt.size();
    nxt.emplace_back(Node());
    tag.emplace_back(0);
  }
 public:
  Trie() : nxt(1), tag(1) {}
  void insert(std::string s) {
    int p = 0;
    for (auto x : s) {
      int c = x - 'a';
      if (nxt[p][c] == 0) addNode(p, c);
      p = nxt[p][c];
    }
    tag[p] = 1;
  }
  int find(std::string s) {
    int p = 0;
    for (auto x : s) {
      int c = x - 'a';
      if (nxt[p][c] == 0) return 0;
      p = nxt[p][c];
    }
    if (tag[p] != 1) return tag[p];
    tag[p] = 2;
    return 1;
  }
};

模板例题：LOJ P2580

01-Trie 求异或最大值

做法：将数的二进制表示看成一个字符串，就可以建出字符集为 {0, 1} 的 Trie 树。把所有数字丢进去建好树之后， 对于这 n 个数中每个数，查找和它当前位不一致的位有没有。有就取，没有只能取自己，然后接着跑到底。

注意这里可以，丢一个进去算一个，也就是说可以支持动态添加。因为要求异或最值，因此我们需要从最高位往最低位建 Trie，因此要统一高度。

class Trie {
  using Node = std::array<int, 2>;
  std::vector<Node> ch;
  void addNode(int fa, int c) {
    ch[fa][c] = ch.size();
    ch.emplace_back(Node());
  }
 public:
  Trie() : ch(1) {}
  void insert(int x) {
    for (int i = 30, p = 0; i >= 0; --i) {
      int c = (x >> i) & 1;
      if (ch[p][c] == 0) addNode(p, c);
      p = ch[p][c];
    }
  }
  int getMax(int x) {
    int r = 0;
    for (int i = 30, p = 0; i >= 0; --i) {
      int c = (x >> i) & 1;
      if (ch[p][c ^ 1]) {
        p = ch[p][c ^ 1];
        r |= (1 << i);
      } else {
        p = ch[p][c];
      }
    }
    return r;
  }
  int getAns(const std::vector<int> &a) {
    int r = 0;
    for (auto x : a) {
      insert(x);
      r = std::max(r, getMax(x));
    }
    return r;
  }
};

典型例题：LOJ P4551

此问题是树上问题，即树上两点路径上的异或和最大。任取一点为根可以将此问题转化成数列问题。

01-Trie (Fusion Tree) 求异或和（支持修改，全局加 1，暂不支持合并）

这里求异或和，可以从最低位往最高位建树节省空间。

class Trie {
  using Node = std::array<int, 4>;
  std::vector<Node> ch;
  #define lson ch[p][0]
  #define rson ch[p][1]
  // ch[p][2] 表示以 p 为根的子树的大小
  // ch[p][3] 表示以 p 为根的子树的异或值
  void addNode(int p, int c) {
    ch[p][c] = ch.size();
    ch.emplace_back(Node());
  }
  void pushUp(int p) {
    ch[p][3] = 0;
    if (lson) ch[p][3] ^= (ch[lson][3] << 1);
    if (rson) ch[p][3] ^= (ch[rson][3] << 1) | (ch[rson][2] & 1);
  }
  // 注意这里 ch[lson][2] = ch[p][2] - ch[rson] 是延迟更新的。
  void insert(int p, int x) {
    ++ch[p][2];
    if (!x) return;
    if (!ch[p][x & 1]) addNode(p, x & 1);
    insert(ch[p][x & 1], x >> 1);
    pushUp(p);
  }
  void erase(int p, int x) {
    --ch[p][2];
    if (!x) return;
    erase(ch[p][x & 1], x >> 1);
    pushUp(p);
  }
  void addAll(int p) {
    if (!ch[p][2]) return;
    if (rson) addAll(rson);
    // 为了进位，先补 0，补 0 的时候记得更新 ch[lson][2]（它延迟更新了）
    if (!lson) addNode(p, 0);
    ch[lson][2] = ch[p][2] - (rson ? ch[rson][2] : 0);
    std::swap(lson, rson);
    pushUp(p);
  }
 public:
  Trie() : ch(1) {}
  void insert(int x) {
    insert(0, x);
  }
  void erase(int x) {
    erase(0, x);
  }
  void addAll() {
    addAll(0);
  }
  int getVal() {
    return ch[0][3];
  }
};

例题：LOJ P6018

注意数据必须保证任意时刻每个节点的矿泉水数非负。

灵活变长版 和 定长版

前缀函数

\[ \pi[i] = \max_{k = 0, \cdots, i} \{ k : s[0, \cdots, k - 1] = s[i - (k - 1), \cdots i] \} \]

即子串 \(s[0, \cdots, i]\) 的最长相等真前缀与真后缀的长度。

注意到两个事实：由定义知 \(\pi[i + 1] \leq \pi[i] + 1\)，因此若 \(s[i + 1] == s[\pi[i]]\)，那 \(\pi[i + 1] = \pi[i] + 1\)，反之，注意到我们始终有 \(s[0, \cdots, \pi[i] - 1] = s[i - \pi[i] + 1, \cdots, i]\)，对于的第二大的长度 \(j\)，我们有： \[ s[0, \cdots, j - 1] = s[i - j + 1, \cdots, i] = s[\pi[i] - j, \cdots, \pi[i] - 1] \] 即 j 等价于字串 \(s[\pi[i] - 1]\) 的前缀和函数值，即 \(j = \pi[\pi[i] - 1]\)，然后依次这样进行下去即可。

复杂度：\(O(n)\)，注意到 \(\pi[i + 1] \leq \pi[i] + 1\)，若取等，我们称为上升（每步最多上升一次），反之我们称为下降，显然严格下降的次数不会超过上升的次数，因此整体上升下降次数不会超过 \(2n\)。

std::vector<int> prefixFunction(std::string s) {
  int n = s.size();
  std::vector<int> p(n);
  for (int i = 1; i < n; ++i) {
    int j = p[i - 1];
    while (j > 0 && s[i] != s[j]) j = p[j - 1];
    if (s[i] == s[j]) ++j;
    p[i] = j;
  }
  return p;
}

注意上述算法是一个在线算法，即可以一个一个的字符添加。

KMP 算法（Knuth-Morris-Pratt 算法）

给定文本 t 和 字符串 s，尝试找到并展示 s 在 t 中的所有出现。

我们可以构建一个字符串 s + # + t，然后求前缀函数即可， 并且注意

1. 函数值最大为 n
2. 若值为 n 表示匹配成功，且 i - 2n 为出现位置
3. 我们不需要保存 t 的信息。

因此我们可以在 \(O(n + m)\) 时间 \(O(n)\) 空间利用前缀函数解决此问题。

// 返回所有匹配在 t 的首位置
std::vector<int> kmp(std::string s, std::string t) {
  std::vector<int> ans;
  int n = s.size(), m = t.size();
  if (n > m) return ans;
  auto p = prefixFunction(s);
  for (int i = 0, j = 0; i < m; ++i) {
    while (j > 0 && s[j] != t[i]) j = p[j - 1];
    if (s[j] == t[i] && ++j == n) ans.emplace_back(i - n + 1);
  }
  return ans;
}

例题：126B，找一个最长的既是前缀又是后缀又是中间的最长字符串。

做法：首先计算出前缀函数，然后，用 kmp 看 s[0, pi[n - 1]] 是否在 s[1, n - 2] 中出现，没出现就看就继续看 \(pi[pi[n - 1] - 1]\) 直到 0 即可。当然了可以有很多细节上的优化（例如 kmp 的时候不用每次都求一次前缀函数，在跑 KMP 的时候也只需要跑一次即可），但是此题不需要，我的代码 也没优化，因为做题主要是测试代码正确性的。

字符串的周期

显然 \(n - \pi[n - 1], n - \pi[pi[n - 1]], \cdots\) 为全部字符串的周期。

统计每个前缀出现的次数

首先以 i 为右端点有长度 \(\pi[i]\) 的前缀，有长度 \(\pi[\pi[i] - 1]\) 的前缀，等等知道长度为 0。

// 返回 长度为 i 的前缀出现的次数
std::vector<int> countPrefix(std::string s) {
  auto p = prefixFunction(s);
  int n = s.size();
  std::vector<int> ans(n + 1);
  for (auto x : p) ++ans[x];
  for (int i = n - 1; i > 0; --i) ans[p[i - 1]] += ans[i];
  for (int i = 0; i <= n; ++i) ++ans[i];
  return ans;
}
// 返回 s 长度为 i 的前缀在 t 中出现的次数
std::vector<int> countPrefix(std::string s, std::string t) {
  auto p = prefixFunction(s);
  int n = s.size(), m = t.size();
  std::vector<int> ans(n + 1);
  for (int i = 0, j = 0; i < m; ++i) {
    while (j > 0 && t[i] != s[j]) j = p[j - 1];
    if (t[i] == s[j]) ++j;
    ++ans[j];
  }
  ++ans[0];
  for (int i = n; i > 0; --i) ans[p[i - 1]] += ans[i];
  return ans;
}

例题：432D 的代码

BM 算法，Sunday 等一系列算法还是下次一定吧

Z-函数，也称拓展 KMP

类似于前缀函数，Z-函数也可以用来求 KMP，也可以 \(O(n)\) 给出 Z-函数，也当作另一种思路。

\(z[i]\) 表示 s 和 \(s[i, n - 1]\) 的最长公共前缀，约定 \(z[0] = 0\)

我们称 \(i, i + z[i] - 1\) 是 i 的匹配段，也称 z-Box。

维护右端点最大的匹配段，记作 \([l, r]\)，即 \(s[l, r]\) 是 s 的前缀。

首先初始化，\(l = r = 0, i = 1\)（始终保证 \(l \leq i\)）

• 若 \(i \leq r\)，根据定义 \(s[i, r] = s[i - l, r - l]\)，若 \(s[i - l] < r - i + 1\)，则 \(z[i] = z[i - l]\)，反之，令 z[i] = r - i + 1 然后暴力拓展直到不能拓展为止
• 若 \(i > r\)，那我们直接暴力求出 \(z[i]\)，

无论那种情况都要更新 r。

std::vector<int> zFunction(std::string s) {
  int n = s.size();
  std::vector<int> z(n);
  for (int i = 1, l = 0, r = 0; i < n; ++i) {
    if (i <= r && z[i - l] < r - i + 1) {
      z[i] = z[i - l];
    } else {
      int j = std::max(0, r - i + 1);
      while (i + j < n && s[j] == s[i + j]) ++j;
      z[i] = j;
      if (i + j - 1 > r) {
        l = i;
        r = i + j - 1;
      }
    }
  }
  return z;
}

复杂度，每次拓展 r 增加 1，因此总拓展次数小于 n，所以整体复杂度 \(O(n)\)。

类似于前缀函数，我们也可以求 KMP

KMP

构造 s + # + t 的串，那么我们可以通过计算 s 的 Z-函数，然后，在 t 中也类似的做，然后如果 t 中找到了长度为 s 长度的 z 值，那么就相当于匹配到了，并且注意到我们在这里不会再更新 r 值。

// 返回所有匹配在 t 的首位置
std::vector<int> kmp(std::string s, std::string t) {
  std::vector<int> ans;
  int n = s.size(), m = t.size();
  if (n > m) return ans;
  auto z = zFunction(s);
  for (int i = 0, l = 0, r = -1; i < m; ++i) {
    if (i > r || z[i - l] >= r - i + 1) {
      int j = std::max(0, r - i + 1);
      while (j < n && i + j < m && s[j] == t[i + j]) ++j;
      if (j == n) ans.emplace_back(i);
      if (i + j - 1 > r) {
        l = i;
        r = i + j - 1;
      }
    }
  }
  return ans;
}

自动机（多模式串匹配）

OI-wiki 上讲的是真的好，就不赘述了。

主要用途，多串匹配。

AC 自动机（Automaton）

以 Trie 机构为基础，结合 KMP 的思想建立的。

• 将所有模式串构成一颗 Trie
• 对 Trie 树上的所有节点构造失配（fail）指针（利用 KMP 思想）。

上面是原始思想，一般都会做两个优化：路径压缩（也称建 Trie 图），后缀链接（也称 last 优化）

路径压缩会改变 Trie 的结构，即改变了状态转移，但是并没有改变最终状态点。它压缩了 fail 指针，一步到位。后缀链接压缩的模式匹配的时候不计入答案的直接跳过。

例题：LOJ P3808

class Automaton {
  inline static const int CHAR = 26;
  using Node = std::array<int, CHAR>;
  std::vector<Node> nxt;
  std::vector<int> cnt, fail, last;
  int charToInt(char x) { return x - 'a';}
  void addNode(int fa, int c) {
    nxt[fa][c] = nxt.size();
    nxt.emplace_back(Node());
    cnt.emplace_back(0);
    fail.emplace_back(0);
    last.emplace_back(0);
  }
 public:
  Automaton() : nxt(1), cnt(1), fail(1), last(1) {}
  void insert(std::string s) {
    int p = 0;
    for (auto x : s) {
      int c = charToInt(x);
      if (nxt[p][c] == 0) addNode(p, c);
      p = nxt[p][c];
    }
    ++cnt[p];
  }
  void build() {
    std::queue<int> Q;
    for (int c = 0; c < CHAR; ++c) {
      if (nxt[0][c]) Q.push(nxt[0][c]);
    }
    while (!Q.empty()) {
      int p = Q.front(); Q.pop();
      for (int c = 0; c < CHAR; ++c) {
        if (int &q = nxt[p][c]; q != 0) {
          fail[q] = nxt[fail[p]][c];
          Q.push(q);
          // 用作模式匹配时计数的优化
          last[q] = cnt[fail[q]] ? fail[q] : last[fail[q]];
        } else {
          q = nxt[fail[p]][c];
        }
      }
    }
  }
  // 具体写法见题目要求
  int query(std::string s) {
    int p = 0, r = 0;
    auto add = [&](int & x) {
      r += x; x = 0;
    };
    for (auto x : s) {
      int c = charToInt(x);
      p = nxt[p][c];
      if (cnt[p]) add(cnt[p]);
      int q = p;
      while (last[q]) {
        q = last[q];
        if (cnt[q]) add(cnt[q]);
      }
    }
    return r;
  }
};

int main() {
  //freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  std::cin >> n;
  Automaton A;
  for (int i = 0; i < n; ++i) {
    std::string s;
    std::cin >> s;
    A.insert(s);
  }
  A.build();
  std::string t;
  std::cin >> t;
  std::cout << A.query(t) << "\n";
  return 0;
}

另外加强版例题：LOJ P3796

我直接骚气的来一波节点存字符

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

class Automaton {
  inline static const int CHAR = 26;
  using Node = std::array<int, CHAR>;
  std::vector<Node> nxt;
  std::vector<int> fail, last;
  int charToInt(char x) { return x - 'a';}
  void addNode(int fa, int c) {
    nxt[fa][c] = nxt.size();
    nxt.emplace_back(Node());
    fail.emplace_back(0);
    last.emplace_back(0);
    str.emplace_back(std::string());
  }
 public:
  Automaton() : nxt(1), str(1), fail(1), last(1) {}
  std::vector<std::string> str;
  void insert(std::string s) {
    int p = 0;
    for (auto x : s) {
      int c = charToInt(x);
      if (nxt[p][c] == 0) addNode(p, c);
      p = nxt[p][c];
    }
    str[p] = s;
  }
  void build() {
    std::queue<int> Q;
    for (int c = 0; c < CHAR; ++c) {
      if (nxt[0][c]) Q.push(nxt[0][c]);
    }
    while (!Q.empty()) {
      int p = Q.front(); Q.pop();
      for (int c = 0; c < CHAR; ++c) {
        if (int &q = nxt[p][c]; q != 0) {
          fail[q] = nxt[fail[p]][c];
          Q.push(q);
          // 用作模式匹配时计数的优化
          last[q] = str[fail[q]].size() ? fail[q] : last[fail[q]];
        } else {
          q = nxt[fail[p]][c];
        }
      }
    }
  }
  // 具体写法见题目要求
  std::vector<int> query(std::string s) {
    std::vector<int> r(str.size());
    int p = 0;
    for (auto x : s) {
      int c = charToInt(x);
      p = nxt[p][c];
      if (str[p].size()) ++r[p];
      int q = p;
      while (last[q]) {
        q = last[q];
        ++r[q];
      }
    }
    return r;
  }
};

int main() {
  //freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n;
  while (std::cin >> n) {
    if (n == 0) break;
    Automaton A;
    for (int i = 0; i < n; ++i) {
      std::string s;
      std::cin >> s;
      A.insert(s);
    }
    A.build();
    std::string t;
    std::cin >> t;
    auto r = A.query(t);
    int x = *std::max_element(r.begin(), r.end());
    std::cout << x << "\n";
    if (x > 0) {
      for (int i = 0; i < r.size(); ++i) if (r[i] == x) {
        std::cout << A.str[i] << "\n";
      }
    }
  }
  return 0;
}

后缀数组 SA（也称后缀排序)

学习资料：诱导排序和 SA-IS，该博文还提供了原论文链接。逐字快速阅读，然后思考，再模拟，再逐字慢阅读掌握（最后还是没完全懂）然后读原始论文 才终于理解了。

流程：首先确定类型 L 和 S，然后 S 中确定 型，然后每一个后缀 \(suf(S, i)\) 的排序改成 它到 \(pre(S, i)\)（第一个 型的这一段）的排序，那么初始所有字符相同的 * 型都是一样大的，所以可以任意排列（丢进桶中），然后用诱导排序，第一步将 L 型的都排好序了，然后根据 L 把所有 S 型 \(suf(S, i)\) 排序（此时做了微小的改变，个人理解）。那么这就给出了 LMS-substring 的排序，那么相同的 LMS-substring 只可能出现在相邻的情况。如果这些 LMS-substring 两两不同，那么它们就直接被排好序，否则 LMS-substring 就递归的进行排序即可。最后 根据 LMS-substring 的排序诱导整体的排序。

// 请确保最后一个元素为 0，且 a 中其它元素都是正整数，且最大值较小。
std::vector<int> SAIS(std::vector<int> a) {
  enum TYPE {L, S};
  int n = a.size() - 1, mx = *std::max_element(a.begin(), a.end()) + 1;
  std::vector<int> SA(n + 1, -1);
  std::vector<int> bucket(mx), lbucket(mx), sbucket(mx);
  for (auto x : a) ++bucket[x];
  for (int i = 1; i < mx; ++i) {
    bucket[i] += bucket[i - 1];
    lbucket[i] = bucket[i - 1];
    sbucket[i] = bucket[i] - 1;
  }
  // 确定 L, S 类型以及 * 型的位置
  std::vector<TYPE> type(n + 1);
  type[n] = S;
  for (int i = n - 1; i >= 0; --i) {
    type[i] = (a[i] < a[i + 1] ? S : (a[i] > a[i + 1] ? L : type[i + 1]));
  }
  // 诱导排序(从 * 型诱导到 L 型、从 L 型诱导到 S 型)
  auto inducedSort = [&]() {
    for (int i = 0; i <= n; ++i) {
      if (SA[i] > 0 && type[SA[i] - 1] == L) {
        SA[lbucket[a[SA[i] - 1]]++] = SA[i] - 1;
      }
    }
    for (int i = 1; i < mx; ++i) {
      sbucket[i] = bucket[i] - 1;
    }
    for (int i = n; i >= 0; --i) {
      if (SA[i] > 0 && type[SA[i] - 1] == S) {
        SA[sbucket[a[SA[i] - 1]]--] = SA[i] - 1;
      }
    }
  };
  // 首先根据诱导排序给出 LMS-prefix 的排序
  std::vector<int> pos;
  for (int i = 1; i <= n; ++i) {
    if (type[i] == S && type[i - 1] == L) {
      pos.emplace_back(i);
    }
  }
  for (auto x : pos) SA[sbucket[a[x]]--] = x;
  inducedSort();
  // 根据 LMS-prefix 的排序给出 LMS-substring 的命名，即得到 S1
  auto isLMSchar = [&](int i) {
    return i > 0 && type[i] == S && type[i - 1] == L;
  };
  auto equalSubstring = [&](int x, int y) {
    do {
      if (a[x] != a[y]) return false;
      ++x; ++y;
    } while (!isLMSchar(x) && !isLMSchar(y));
    return a[x] == a[y];
  };
  // 注意到因为 LMS-prefix 排序会导致仅有相邻的 LMS-substring 才可能相等
  std::vector<int> name(n + 1, -1);
  int lx = -1, cnt = 0;
  bool flag = true; // 表示无相同的 LMS-substring
  for (auto x : SA) if (isLMSchar(x)) {
    if (lx >= 0 && !equalSubstring(lx, x)) ++cnt;
    if (lx >= 0 && cnt == name[lx]) flag = false;
    name[x] = cnt;
    lx = x;
  }
  std::vector<int> S1;
  for (auto x : name) if (x != -1) S1.emplace_back(x);
  auto getSA1 = [&]() {
    int n1 = S1.size();
    std::vector<int> SA1(n1);
    for (int i = 0; i < n1; ++i) SA1[S1[i]] = i;
    return SA1;
  };
  auto SA1 = flag ? getSA1() : SAIS(S1);
  // 再次诱导排序，根据 S1 的排序得到 SA
  lbucket[0] = sbucket[0] = 0;
  for (int i = 1; i < mx; ++i) {
    lbucket[i] = bucket[i - 1];
    sbucket[i] = bucket[i] - 1;
  }
  std::fill(SA.begin(), SA.end(), -1);
  // 这里是逆序扫描 SA1，因为 SA 中 S 型桶是倒序的
  for (int i = SA1.size() - 1; i >= 0; --i) {
    SA[sbucket[a[pos[SA1[i]]]]--] = pos[SA1[i]];
  }
  inducedSort();
  return SA;
}

std::vector<int> SAIS(const std::string &s) {
  // s 的字符集为小写字，则可使用下面函数。
  // auto f = [](char x) -> int { return int(x - 'a') + 1;};
  auto f = [](char x) -> int { return int(x) + 1;};
  std::vector<int> a;
  for (auto c : s) a.emplace_back(f(c));
  a.emplace_back(0);
  auto sa = SAIS(a);
  return std::vector<int>(sa.begin() + 1, sa.end());
}

找在 T 中子串 S

注意这里可以先给定 T，再一个个给 S。而 KMP，AC 自动机都是先给 S 再给 T。

若 S 是 T 的子串，那么 S 必然是 T 的后缀的前缀。因为后缀已经被排序了，因此我们可以二分解决。因此复杂度为 \(O(|S| \log|T|)\)，出现次数也可以通过二分得到，并且输出位置也很轻松哈哈。

从字符串首尾取字符最小化字典序

例题：LOJ P2870

给一个正串和反串，每次取一个字典序更小的串中的首字符。那么我们可以把这两个串拼起来，然后求后缀数组比较即可。

height 数组 和 最长公共前缀 LCP

我们定义 \(ht[i] = lcp(sa[i], sa[i - 1])\) 即第 i 名的后缀和它前一名的后缀的最长公共前缀，约定 \(ht[0] = 0\)。

我们断言：\(ht[rk[i]] \geq ht[rk[i - 1]] - 1\)。

证明：若 \(ht[rk[i - 1]] > 1\)，设后缀 i - 1 为 aAD（其中 \(|A| = ht[rk[i - 1]] - 1\)）则后缀 i 就是 AD，\(sa[rk[i - 1]]\) 的后缀为 aAB，且 \(B < D\)，所以 \(sa[rk[i - 1]] + 1\) 的后缀为 AB 必然在 i 的前面，因此 \(sa[rk[i] - 1]\) 的前缀必然包含 A（存在一个比我小的跟我有相同的后缀 A，那么必然我的上一个必然也有相同的前缀 A)，证毕。

std::string s;
std::cin >> s;
int n = s.size();
auto sa = SAIS(s);
std::vector<int> rk(n);
for (int i = 0; i < n; ++i) rk[sa[i]] = i;
// 可能从 1 开始编号会方便点，但是我不喜欢。
std::vector<int> ht(n);
for (int i = 0, k = 0; i < n; ++i) {
  if (k) --k;
  if (rk[i] == 0) k = 0;
  else {
    // 字符串不必担心越界，否则最好添加一个唯一的最小元素。
    while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
    ht[rk[i]] = k;
  }
}

\(lcp(sa[i], sa[j]] = \min(ht[i + 1, \cdots, j])\)，所以可以用线段树解决。

不同子串的数量

\(\frac{n(n + 1)}{2} - \sum_{i = 1}^{n - 1} ht[i]\)

第 k 小的子串

例题：TJOI2015 的提交答案

如果不同位置的相同子串算作一个，那么直接利用 ht 数组就可以轻松的 \(O(n)\) 构造，每次 \(\log(n)\) 查询。

如果不同位置的相同子串算作多个，那么 ht 数组就没用了，我们可以一个个的查找 \(O(n)\) 构造，\(O(n \log n)\) 查询。

后缀自动机 SAM

字符串 s 的 SAM 是一个接受 s 的所有后缀的最小 DFA（确定性有限自动机或确定性有限状态自动机）。

广义后缀自动机(Trie + SAM)

后缀自动机 (suffix automaton, SAM) 是用于处理单个字符串的子串问题的强力工具 广义后缀自动机 (General Suffix Automaton) 则是将后缀自动机整合到字典树中来解决对于多个字符串的子串问题。

序列自动机

仅接受一个字符串的子序列的自动机。

例题：HEOI2015

最小表示法

我们称两个字符串 S 和 T 循环同构，如果它们各自首尾相接得到一个有向环是相同的。

最小表示：与 S 循环同构的字典序最小的字符串。

我们记 \(S_i\) 表示以 S 的第 i 个字符开头与 S 循环同构的字符串。

直接暴力是 \(O(n^2)\) 的，但是观察到，若 \(s[i, \cdots, i +k - 1] = s[j \cdot, j + k - 1]\)，那么我们就要开始比较 s[i + k] 和 s[j + k]，不妨设 \(s[i + k] > s[j + k]\)，那么显然 \(S_{i + p} < S_{j + p} (p \leq k)\) 若 \(l \in [i, i + k]\)，则 \(S_l\) 不可能成为最小表示。

模板例题：LOJ P1368 和 UVA 719

template<typename T>
int minPresent(std::vector<T>& a) {
  int k = 0, i = 0, j = 1, n = a.size();
  while (k < n && i < n && j < n) {
    if (a[(i + k) % n] == a[(j + k) % n]) {
      ++k;
    } else {
      a[(i + k) % n] > a[(j + k) % n] ? i += k + 1 : j += k + 1;
      if (i == j) ++i;
      k = 0;
    }
  }
  return std::min(i, j);
}

Lyndon 分解

Lyndon word：我们称 \(s\) 是 Lyndon word，如果 s 的字典序严格小于它所有真后缀的字典序。这等价于说它是自己的循环同构中最小的。

Lyndon 分解：\(s = w_1 \cdots, w_k\)，其中 \(w_i\) 是 Lyndon word，且 \(w_1 \geq w_2 \geq \cdots, w_k\)。可以证明分解存在且唯一。

Duval 算法：在 \(O(n)\) 时间给出一个串的 Lyndon 分解。

根据 Shirshov 分解：\(s = s_L s_R\)，其中 \(s_R\) 是字典序最小的后缀（从而是 Lyndon word），若 \(s_R = s\) 结束；否则，我们对剩下的 \(s_L\) 做同样的操作。但是因为后缀数组算法本身太复杂（太长），所以还是推荐 Duval 算法。

这个算法具体说就是让 \(s = w \cdots w \hat{w} x\)，其中 w 是 Lyndon word，\(\hat{w}\) 是 w 的前缀，\(x\) 是还未考虑到的剩余部分。注意到此时我们还不能说 w 是 s 的 Lyndon 分解的一部分，因为如果 \(\hat{w} x[0] > w\)（此时就不是了，此时就变成了一个新的 Lyndon word）。而如果 \(\hat{w} x[0]\) 还是 w 的前缀，那就把它吸收进去，继续考虑。如果 \(\hat{w} x[0] < w\)，那么此时 w 确实是 Lyndon 分解的一部分，把这些 w 全踢出去即可。

模板例题：LOJ P6114

// Lyndon decomposition using Duval algorithm
std::vector<std::string> duval(const std::string &s) {
  std::vector<std::string> r;
  int n = s.size(), i = 0;
  while (i < n) {
    int j = i + 1, k = i;
    while (j < n && s[k] <= s[j]) {
      if (s[k] < s[j]) k = i;
      else ++k;
      ++j;
    }
    while (i <= k) {
      r.emplace_back(s.substr(i, j - k));
      i += j - k;
    }
  }
  return r;
}

一个用途：双拼 s 可求最小表示。（但是最小表示本身代码比较简单所以意义也不是很大）

回文子串的 Manacher 算法

问题：给定字符串 s，求所有回文子串。

首先注意到以一个位置为中心的最长回文串的子串都是回文子串，因此我们直到对每个位置 i，求它们的半径 \(d_i\) 即可。而 Manacher 给出了一个 \(O(|s|)\) 时空的算法。由于回文串长度的奇偶性使得要分两种情况讨论，但是我们其实也可以在其中插入 # 来统一成奇数的形式。

模板例题：UVA-11475

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

// 仅仅处理奇数长回文串，这个实现像极了 Z-函数
std::vector<int> Manacher(std::string s) {
  int n = s.size();
  std::vector<int> d(n);
  for (int i = 0, l = 0, r = -1; i < n; ++i) {
    int k = i > r ? 1 : std::min(d[l + r - i], r - i);
    while (k <= i && i + k < n && s[i - k] == s[i + k]) ++k;
    d[i] = k--;
    if (i + k > r) {
      l = i - k;
      r = i + k;
    }
  }
  return d;
}

int main() {
  //freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::string s;
  while (std::cin >> s) {
    std::string ss("#");
    std::swap(ss, s);
    for (auto x : ss) {
      s += x; s += '#';
    }
    auto d = Manacher(s);
    int now = 0;
    while (now < s.size() && now + d[now] != s.size()) ++now;
    std::cout << ss;
    for (int i = now - d[now]; i >= 0; --i) if (s[i] != '#') std::cout << s[i];
    std::cout << "\n";
  }
  return 0;
}

其它例题：LOJ P4555，求最长双回文子串（即可以拆成两个回文子串）

我们定义 \(l[i], r[i]\) 分别表示以 i 开头和以 i 结尾的回文长度。则 \[ l[i] = \max(l[i], l[i + 2] - 2), r[i] = \max(r[i], r[i - 2] - 2) \] 枚举每一个 # 为断点，更新答案即可。

#include <bits/stdc++.h>
#define watch(x) std::cout << (#x) << " is " << (x) << std::endl
using LL = long long;

// 仅仅处理奇数长回文串
std::vector<int> Manacher(std::string s) {
  int n = s.size();
  std::vector<int> d(n);
  for (int i = 0, l = 0, r = -1; i < n; ++i) {
    int k = i > r ? 1 : std::min(d[l + r - i], r - i);
    while (k <= i && i + k < n && s[i - k] == s[i + k]) ++k;
    d[i] = k--;
    if (i + k > r) {
      l = i - k;
      r = i + k;
    }
  }
  return d;
}

int main() {
  //freopen("in", "r", stdin);
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  std::string s;
  std::cin >> s;
  std::string ss("#");
  std::swap(ss, s);
  for (auto x : ss) {
    s += x; s += '#';
  }
  auto d = Manacher(s);
  int n = s.size();
  std::vector<int> l(n), r(n);
  auto cmax = [](int &x, int y) {
    if (x < y) x = y;
  };
  for (int i = 0; i < n; ++i) {
    cmax(l[i + d[i] - 1], d[i] - 1);
    cmax(r[i - d[i] + 1], d[i] - 1);
  }
  for (int i = n - 3; i >= 0; i -= 2)  cmax(l[i], l[i + 2] - 2);
  for (int i = 2; i < n; i += 2) cmax(r[i], r[i - 2] - 2);
  int ans = 0;
  for (int i = 2; i < n; i += 2) if (l[i] && r[i]) cmax(ans, l[i] + r[i]);
  std::cout << ans << "\n";
  return 0;
}

回文自动机

用于存储一个串中所有回文子串的高效数据结构。