palindromic_automaton.hpp¶

#include "noya/palindromic_automaton.hpp"

SourceExpanded

#ifndef NOYA_PALINDROMIC_AUTOMATON_HPP
#define NOYA_PALINDROMIC_AUTOMATON_HPP 1

#include <array>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sigma = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sigma> next;
    int fail, len, cnt;

    Node(int fail, int len) : fail(fail), len(len), cnt(0) {
      std::fill(next.begin(), next.end(), 0);
    }
  };

  std::vector<Node> nodes;
  std::vector<int> s;
  int last = 0;

  palindromic_automaton() {
    nodes.push_back(Node(1, 0));
    nodes.push_back(Node(0, -1));
    s.push_back(-1);
    last = 0;
  }

  int get_fail(int x) {
    while (s[int(s.size()) - 1 - nodes[x].len - 1] != s.back()) {
      x = nodes[x].fail;
    }
    return x;
  }

  /// @brief Append character c (in [0, sigma)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sigma);
    s.push_back(c);
    int cur = get_fail(last);
    if (!nodes[cur].next[c]) {
      int now = int(nodes.size());
      int fail = nodes[get_fail(nodes[cur].fail)].next[c];
      nodes.push_back(Node(fail, nodes[cur].len + 2));
      nodes[cur].next[c] = now;
    }
    last = nodes[cur].next[c];
    nodes[last].cnt++;
    return last;
  }

  /// @brief Return the number of nodes in the automaton.
  int size() const { return int(nodes.size()); }
};

} // namespace noya

#endif // NOYA_PALINDROMIC_AUTOMATON_HPP

#include <array>
#include <cassert>
#include <vector>

namespace noya {

/// @brief Palindromic automaton (Eertree) for enumerating distinct palindromic substrings.
template <int sigma = 26> struct palindromic_automaton {
  struct Node {
    std::array<int, sigma> next;
    int fail, len, cnt;

    Node(int fail, int len) : fail(fail), len(len), cnt(0) {
      std::fill(next.begin(), next.end(), 0);
    }
  };

  std::vector<Node> nodes;
  std::vector<int> s;
  int last = 0;

  palindromic_automaton() {
    nodes.push_back(Node(1, 0));
    nodes.push_back(Node(0, -1));
    s.push_back(-1);
    last = 0;
  }

  int get_fail(int x) {
    while (s[int(s.size()) - 1 - nodes[x].len - 1] != s.back()) {
      x = nodes[x].fail;
    }
    return x;
  }

  /// @brief Append character c (in [0, sigma)) and return the node id of the new longest palindromic suffix.
  int extend(int c) {
    assert(0 <= c && c < sigma);
    s.push_back(c);
    int cur = get_fail(last);
    if (!nodes[cur].next[c]) {
      int now = int(nodes.size());
      int fail = nodes[get_fail(nodes[cur].fail)].next[c];
      nodes.push_back(Node(fail, nodes[cur].len + 2));
      nodes[cur].next[c] = now;
    }
    last = nodes[cur].next[c];
    nodes[last].cnt++;
    return last;
  }

  /// @brief Return the number of nodes in the automaton.
  int size() const { return int(nodes.size()); }
};

} // namespace noya