Counting Patterns#2604

Counting Patterns (Editorial)

Let us build the Aho — Corasick automaton for the set of patterns. The total length of the patterns does not exceed 5 \cdot 10^5, so the trie contains at most 5 \cdot 10^5 + 1 vertices, and the alphabet consists of lowercase Latin letters. For each pattern we store the number of the vertex where it ends. Equal patterns end at the same vertex.

Processing the text. Let us run the text through the automaton. After reading the next character, the automaton is at the vertex corresponding to the longest suffix of the text read so far that is a prefix of some pattern. Increase the counter by . In the end, equals the number of text positions at which the automaton was at vertex .

Counting occurrences. Pattern ends at the current text position if and only if the vertex lies on the chain of suffix links v \to \mathit{link}[v] \to \ldots \to 0. In other words, vertex "is counted" at all positions where the automaton was at the vertices of its subtree in the suffix link tree (the parent of vertex in this tree is ). Therefore, the number of occurrences of the string of vertex equals the sum of over the subtree of vertex .

Following the chain of links after each character of the text is not allowed: the chains can be long. Instead, we compute the subtree sums once at the end. A suffix link leads to a vertex of smaller depth, and breadth-first search visits the vertices in non-decreasing order of depth. Hence, if we go through the vertices in reverse breadth-first order and for each vertex perform \mathit{cnt}[\mathit{link}[u]] \mathrel{+}= \mathit{cnt}[u], then by the time a vertex is processed, its counter already holds the sum over its entire subtree.

The answer for pattern equals .

Complexity. Building the automaton takes O(V \cdot 26), where is the number of trie vertices, processing the text takes , accumulating the counters takes , and printing the answers takes . The transition array takes about 5 \cdot 10^5 \cdot 26 \cdot 4 bytes MB.

Example

The text is , the patterns are , , , . Insert the patterns into the trie in the given order. The vertex numbers correspond to the order of their creation, and the terminal vertices are highlighted: \mathit{endNode} = (2, 4, 6, 7).

Suffix links: \mathit{link}[2] = 5 (ab \to b), \mathit{link}[3] = 7 (ac \to c), \mathit{link}[4] = 5 (acb \to b), \mathit{link}[6] = 1 (ba \to a). The links of vertices , , lead to the root. Breadth-first search visits the vertices in the order 0, 1, 5, 7, 2, 3, 6, 4.

Let us run the text through the automaton. Under each character, the vertex where the automaton ends up after reading it is shown.

For example, after reading (position ), the automaton is at vertex (). The pattern also ends at this position, but the automaton is not at its vertex ; it is at vertex , from which a suffix link leads to vertex . This is exactly why the counters have to be summed over the suffix link tree.

The numbers of visits of the vertices are \mathit{cnt} = (0, 2, 3, 1, 0, 1, 2, 2) for vertices 0, \ldots, 7. We go through the vertices in reverse breadth-first order 4, 6, 3, 2, 7, 5, 1 and add the counter of each vertex to the counter of its suffix link. The figure shows the suffix link tree; for each vertex, the number of visits and the final sum over its subtree are given.

Answers: \mathit{cnt}[2] = 3 (), \mathit{cnt}[4] = 0 (), \mathit{cnt}[6] = 2 (), \mathit{cnt}[7] = 1 + 2 = 3 ().

Algorithm Implementation

Declare the constants and the working arrays. The array stores the transitions of the automaton, stores the suffix links, and is the number of visits of vertex (and after accumulation, the number of occurrences of its string in the text). The variable contains the current number of vertices; the root is vertex . The vector stores the breadth-first order of the vertices.

#define ALPH 26
#define MAXN 500005
int go_[MAXN][ALPH];
int link_[MAXN];
int cnt[MAXN];
int sz = 1;
vector<int> order;

The function addString inserts the pattern into the trie and returns the number of the vertex where it ends.

int addString(const string &s)
{
  int v = 0;
  for (char ch : s)
  {
    int c = ch - 'a';
    if (!go_[v][c]) go_[v][c] = sz++;
    v = go_[v][c];
  }
  return v;
}

The function buildAutomaton uses breadth-first search to compute the suffix links and complete the transitions of the automaton.

void buildAutomaton()
{
  queue<int> q;
  q.push(0);
  while (!q.empty())
  {

Each vertex extracted from the queue is added to the vector .

    int v = q.front(); q.pop();
    order.push_back(v);

If the trie has a transition v \to u by the character , then the suffix link of vertex equals \mathit{go\_}[\mathit{link\_}[v]][c] (for the children of the root it is the root), and vertex is pushed into the queue. Otherwise the transition is completed: from vertex by the character the automaton moves to the same vertex as from .

    for (int c = 0; c < ALPH; c++)
    {
      int u = go_[v][c];
      if (u)
      {
        link_[u] = (v == 0) ? 0 : go_[link_[v]][c];
        q.push(u);
      }
      else
        go_[v][c] = (v == 0) ? 0 : go_[link_[v]][c];
    }
  }
}

The main part of the program. Read the text and the number of patterns .

cin >> text >> k;

Read the patterns, insert them into the trie and store the numbers of their end vertices in the array .

vector<int> endNode(k);
string p;
for (int i = 0; i < k; i++)
{
  cin >> p;
  endNode[i] = addString(p);
}

Build the Aho — Corasick automaton.

buildAutomaton();

Run the text through the automaton and count how many times the automaton visited each vertex.

int v = 0;
for (char ch : text)
{
  v = go_[v][ch - 'a'];
  cnt[v]++;
}

Go through the vertices in reverse breadth-first order (except the root) and add the counter of vertex to the counter of its suffix link. After that, equals the sum of visits over the subtree of vertex in the suffix link tree.

for (int i = (int)order.size() - 1; i > 0; i--)
{
  int u = order[i];
  cnt[link_[u]] += cnt[u];
}

The number of occurrences of pattern equals the counter of its end vertex.

for (int i = 0; i < k; i++)
  cout << cnt[endNode[i]] << '\n';