Замечания к реализации бора и структуры Ахо-Корасик.

Опечатки, баги и конструктивная критика принимаются (Антон Тимофеев).

Бор

Самая простая структура вершины:

struct Vertex
{
  static const int alphabet = 256;
  Vertex* to[alphabet];                     // указатели на смежные вершины, NULL - если нет ребра

  Vertex() { memset(to, 0, sizeof(NULL)); } // конструктор пустой новой вершины
};

Если хотим cжать бор, убрав лишние ребра в вершинах со степенями 0 и 1, то структура следующая:

struct Vertex
{
  static const int alphabet = 256;
  char prevc;  // символ, по которому мы пришли из родителя
  int degree;  // степень вершины 0, 1 или alphabet
  Vertex** to; // degree == 0 => NULL
               // degree == 1 => (Vertex*)to - указатель на смежную вершину
               // degree >= 2 => to - указатель на первую вершину в массиве указателей на смежные

  Vertex( char prevc ) : prevc(prevc), degree(0), to(NULL) { }

  /* Переход по символу c, равно NULL, если не существует перехода */
  Vertex* To( char c )
  {
    if (degree == 0)
      return NULL;
    if (degree == 1)
      return (Vertex *)to->prevc == c ? (Vertex*)to : NULL;
    return to[c];
  }

  /* Переход по символу, создающий новое ребро, если ещё не было */
  Vertex* Access( char c )
  {
    if (degree == 0)
    {
      to = new Vertex(c);
      degree++;
      return to;
    }
    if (degree == 1)
    {
      if ((Vertex*)to->prevc == c)
        return (Vertex*)to;
      Vertex** edges = new Vertex*[alphabet];
      edges[(Vertex*)to->prevc] = (Vertex*)to;
      to = edges;
    }
    if (to[c] == NULL)
      to[c] = new Vertex(c);
    return to[c];
  }
};

Ахо-Корасик

Сжимать бор c Ахо-Корасик бесполезно, если хранить все функции переходов next(v, c) для каждой вершины (всё равно тратим O(|Σ|·Σs_i) памяти).

struct Vertex
{
  const int alphabet = 256;
  Vertex* prev;           // ссылка на родителя
  char    prevc;          // символ, по которому мы пришли из родителя
  Vertex* to[alphabet];   // указатели на смежные вершины, NULL - если нет ребра

  Vertex* suff;           // суффиксная ссылка, здесь хранится предподсчёт для Suff(v)
  Vertex* next[alphabet]; // предподсчёт для функции переходов Next(v, c)

  Vertex( Vertex* prev, char prevc ) : prev(prev), prevc(prevc), suff(NULL)
  {
    memset(to, 0, sizeof(to));
    memset(next, 0, sizeof(next));
  }
  /* Переход по символу, создающий новое ребро, если ещё не было */
  Vertex* Access( char c )
  {
    if (to[c] == NULL)
      to[c] = new Vertex(this, c);
    return to[c];
  }
  /* Вычисление суффиксной ссылки с запоминанием */
  Vertex* Suff()
  {
    if (suff != NULL)
      return suff;
    return suff = prev->Suff()->Next(v->prevc);
  }
  /* Функция перехода с запоминанием */
  Vertex* Next( char c )
  {
    if (next[c] != NULL)
      return next[c];
    if (to[c] != NULL)
      return next[c] = to[c];
    return next[c] = Suff()->Next(c);
  }
};

Перед использованием методов Suff и Next необходимо вызвать от построенного бора функцию Init(root).

void Init( Vertex*& root )
{
  assert(root != NULL);
  root->suff = root;
  for (int i = 0; i < root->alphabet; i++)
    if (root->to[i] != NULL)
      root->to[i]->suff = root;
  for (int i = 0; i < root->alphabet; i++)
    root->next[i] = root->to[i] != NULL ? root->to[i] : root;
}