字符串

hj23308 · 2024-05-07 23:09:23 · 个人记录

Trie

[return id] trie

struct Trie {
  struct Node {
    int trans[maxC];

    Node() { std::fill(trans, trans + maxC, -1); }
  };

  int tot;
  std::vector<Node> tree;

  int New(Node val = Node()) {
    tree.emplace_back(val);
    return tot++;
  }

  Trie() { New(); }

  int Extend(int p, int c) {
    int cur = tree[p].trans[c];
    if (cur == -1) cur = New();
    return tree[p].trans[c] = cur;
  }

  std::vector<std::pair<int, int>> Trans(int p) {
    std::vector<std::pair<int, int>> res;
    for (int i = 0, v; i < maxC; i++)
      if (~(v = tree[p].trans[i]))
        res.emplace_back(v, i);
    return res;
  }
};

General SAM

[return id] general sam

struct SAM {
  struct Node {
    int len, link, trans[maxC]{};

    Node() { len = link = 0; }
  };

  int tot{};
  std::vector<Node> tree;

  int New(Node val = Node()) {
    tree.emplace_back(val);
    return tot++;
  }

  SAM() { New(); }

  int extend(int p, int c) {
    int cur = New();
    tree[cur].len = tree[p].len + 1;
    while (p && !tree[p].trans[c]) { tree[p].trans[c] = cur, p = tree[p].link; }
    if (tree[p].trans[c]) {
      int q = tree[p].trans[c];
      if (tree[q].len == tree[p].len + 1) {
        tree[cur].link = q;
      } else {
        int cl = New(tree[q]);
        tree[cl].len = tree[p].len + 1;
        while (tree[p].trans[c] == q) {
          tree[p].trans[c] = cl, p = tree[p].link;
        }
        tree[q].link = tree[cur].link = cl;
      }
    } else {
      tree[p].trans[c] = cur, tree[cur].link = 0;
    }
    return cur;
  }
};