Finding Patterns#2603

Finding 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. The alphabet consists of lowercase Latin letters. A vertex where a pattern ends is marked as terminal, and for each pattern we store the number of its end vertex . Equal patterns end at the same vertex.

Processing the text. Let us run the text through the automaton. Suppose that after reading the next character the automaton is at vertex . Then the vertices on the chain of suffix links v \to \mathit{link}[v] \to \ldots \to 0 correspond to all suffixes of the text read so far that are prefixes of patterns. A pattern occurs in the text ending at the current position if and only if its end vertex lies on this chain. Hence, it is enough to mark with the flag all vertices that the chains of suffix links pass through. The answer for pattern is the value .

Why the whole chain cannot be traversed. The length of a chain can be of the order of the pattern length. For example, for the patterns , , , and the text , a long chain would have to be traversed at every position, and the total time would be O(n \cdot L), where is the length of the longest pattern. Therefore, the chain traversal stops in two cases:

The second statement holds because, when vertex is marked, the traversal always continues along its suffix link and stops only at a vertex with \mathit{term} = \textbf{\textit{false}} or at an already marked vertex. Thus, each vertex is marked at most once.

Complexity. Building the automaton takes O(V \cdot 26), where V \le 5 \cdot 10^5 + 1 is the number of trie vertices. Processing the text takes transitions plus markings, and the answers are printed in . 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, the string of each vertex is written under it, and terminal vertices are highlighted: \mathit{endNode} = (3, 6, 9).

Suffix links that do not lead to the root:

No suffix link leads to a terminal vertex, so \mathit{term} = \textbf{\textit{true}} only at vertices , and .

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

char

vertex string

marked vertices

0

4

—

1

7

—

2

8

—

3

9

9 ()

4

3

3 ()

5

0

—

6

0

—

After the character with index , the automaton is at the terminal vertex (): it is marked, and the chain traversal stops at the vertex \mathit{link}[9] = 2, for which \mathit{term}[2] = \textbf{\textit{false}}. The next character is : the trie has no transition from vertex by , and via the suffix link the automaton moves to vertex \mathit{go}[2][b] = 3 (), which is also marked. Vertex () is never marked.

Answer: \mathit{vis}[3] = \textbf{\textit{true}}, \mathit{vis}[6] = \textbf{\textit{false}}, \mathit{vis}[9] = \textbf{\textit{true}}, that is, YES, NO, YES.

Stopping the traversal by the flag. Consider the patterns , , and the text . The trie is a chain of vertices (), (), (), all of them terminal, and the suffix links lead 3 \to 2 \to 1 \to 0.

step

chain traversal

marked

1

1

1 \to 0 (\mathit{term}[0] = \textit{false})

1

2

2

2 \to 1 (\mathit{vis}[1] = \textit{true})

2

3

3

3 \to 2 (\mathit{vis}[2] = \textit{true})

3

4

3

(\mathit{vis}[3] = \textit{true})

—

Each vertex is marked exactly once. Without the flag , starting from the second step, the chain would have to be traversed to the root again each time.

Algorithm Implementation

Declare the constants: the alphabet size and the maximum number of trie vertices.

const int ALPH = 26;
const int MAXN = 500000 + 5;

The array stores the transitions of the automaton, and stores the suffix links. The flag means that the end of a pattern is reachable from vertex via suffix links, and means that vertex has already been visited while processing the text. The variable contains the current number of vertices; the root is vertex .

int go_[MAXN][ALPH];
int link_[MAXN];
bool term[MAXN], vis[MAXN];
int sz = 1;

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];
  }
  term[v] = true;
  return v;
}

The function buildAutomaton uses breadth-first search to compute the suffix links, complete the transitions of the automaton and compute the flags . Push the root of the trie into the queue.

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

Extract a vertex from the queue. The vertex was processed earlier, so its flag is already final, and the flag is supplemented with the flag \mathit{term}[\mathit{link\_}[v]].

  while (!q.empty())
  {
    int v = q.front(); q.pop();
    term[v] = term[v] || term[link_[v]];

Iterate over all characters . 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.

    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);
      }

If there is no transition in the trie, it is completed: from vertex by the character the automaton moves to the same vertex as from . From the root, a missing transition leads to the root.

      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.

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

After each transition, go along the chain of suffix links from the current vertex and mark the vertices. The traversal stops if there are no pattern ends on the rest of the chain (\mathit{term}[u] = \textbf{\textit{false}}) or vertex is already marked.

  for (int u = v; term[u] && !vis[u]; u = link_[u])
    vis[u] = true;
}

Pattern occurs in the text if and only if its end vertex is marked.

for (int i = 0; i < k; i++)
  cout << (vis[endNode[i]] ? "YES" : "NO") << '\n';