If for each string of the set we search for every pattern separately, then with a total input size of up to MB and patterns there will be too many operations. Let us build the Aho — Corasick automaton for the set and check each string of in a single pass over its characters.
Trie. Insert all patterns into a trie. The strings consist of ASCII characters with codes from to , so the transitions are stored in an array of size indexed directly by the character code. There are at most patterns, each of length at most ; hence the trie contains at most 100 \cdot 80 + 1 vertices. A vertex where a pattern ends is marked as terminal.
Automaton. Using breadth-first search, we compute the suffix links and complete the transitions of the automaton: \mathit{go}[v][c] is the vertex to which the automaton moves from by the character . After that, every vertex has a transition by any character, and there is no need to follow suffix links while processing a string.
The flag. The string read by the automaton so far ends with some pattern if and only if a terminal vertex is reachable from the current vertex along the chain of suffix links. Therefore, for each vertex we compute the flag
The vertices are processed in breadth-first order, and the vertex is closer to the root than , so by the time is processed, the value \mathit{term}[\mathit{link}[v]] is already final.
Checking a string. For the next string of we start at the root and move along its characters. If after some transition we are at a vertex with \mathit{term}[v] = \textbf{\textit{true}}, then the prefix of the string just read ends with some pattern, that is, the string contains a pattern as a substring. The remaining characters need not be read: the string is printed. If the string is read to the end and the flag was never met, it contains no pattern.
Input. The strings of the set may contain spaces, so they are read with the function getline. After reading the number , the rest of the first line must be read. An empty string cannot contain a non-empty pattern, so it is never printed.
Complexity. Building the automaton takes O(V \cdot 128), where V \le 8001 is the number of trie vertices. Each string of is processed in time proportional to its length, so the whole search runs in , where is the total size of the input. The transition array takes about 8001 \cdot 128 \cdot 4 bytes MB.
Example
The set of patterns is T = \{abc, bca, aba, bcc, aac\}. Insert the patterns into the trie in the given order. The vertex numbers correspond to the order of their creation; under each vertex the string it corresponds to is written. Terminal vertices are highlighted, and the pattern is shown next to them.
Let us compute the suffix links. The suffix link of a vertex leads to the vertex corresponding to the longest proper suffix of its string that is present in the trie:
\mathit{link}(ab) = b, that is, \mathit{link}[2] = 4;
\mathit{link}(aa) = a, that is, \mathit{link}[9] = 1;
\mathit{link}(abc) = bc, that is, \mathit{link}[3] = 5;
\mathit{link}(aba) = a: the suffix is not in the trie, so \mathit{link}[7] = 1;
\mathit{link}(bca) = a: the suffix is not in the trie, so \mathit{link}[6] = 1;
for the vertices , , , and , no proper non-empty suffix occurs in the trie, so their suffix links lead to the root.
No suffix link leads to a terminal vertex, so the flags coincide with the marks of pattern ends: \mathit{term} = \textbf{\textit{true}} only at vertices , , , and .
The table shows the suffix links, the flags and the transitions of the automaton by the characters , , . Transitions absent in the trie are completed using suffix links. By all other characters, the automaton moves from any vertex to the root.
string | \boldsymbol{\mathit{go}['a']} | \boldsymbol{\mathit{go}['b']} | \boldsymbol{\mathit{go}['c']} | |||
0 | 0 | false | 1 | 4 | 0 | |
1 | 0 | false | 9 | 2 | 0 | |
2 | 4 | false | 7 | 4 | 3 | |
3 | 5 | true | 6 | 4 | 8 | |
4 | 0 | false | 1 | 4 | 5 | |
5 | 0 | false | 6 | 4 | 8 | |
6 | 1 | true | 9 | 2 | 0 | |
7 | 1 | true | 9 | 2 | 0 | |
8 | 0 | true | 1 | 4 | 0 | |
9 | 1 | false | 9 | 2 | 10 | |
10 | 0 | true | 1 | 4 | 0 |
For example, the trie has no transition from vertex () by the character . The automaton takes the transition from the vertex \mathit{link}[9] = 1 (): \mathit{go}[9][b] = \mathit{go}[1][b] = 2. Indeed, after reading , the longest suffix that is a prefix of some pattern is .
Let us run the strings of the set through the automaton. Under each character, the vertex where the automaton ends up after reading it is shown.
: the automaton passes through the vertices , , , , , , . None of them is terminal, so the string is not printed.
: after reading the automaton is at vertex (), and by the character it moves to vertex (), for which \mathit{term} = \textbf{\textit{true}}. The string contains the pattern and is printed; the remaining characters are not read.
: the vertices are , , , , , ; no pattern is found.
: after the automaton is at vertex (), and by the character it moves to the terminal vertex (). The string is printed.
The answer consists of the strings and .
Algorithm Implementation
Declare the constants. The alphabet of the automaton consists of characters, and the character codes serve as indices. The maximum number of trie vertices is 100 \cdot 80 plus a small reserve.
const int ALPH = 128; // ASCII codes 32..126
const int MAXN = 100 * 80 + 5; // maximum number of trie verticesThe array stores the transitions of the automaton, stores the suffix links, and is the flag that the end of a pattern is reachable from vertex via suffix links. The variable contains the current number of vertices; the root is vertex . Global arrays are initially filled with zeros, so a zero value of \mathit{go\_}[v][c] in the trie means that there is no transition.
int go_[MAXN][ALPH]; // transitions of the automaton
int link_[MAXN]; // suffix links
bool term[MAXN]; // the end of a pattern is reachable
// from the vertex via suffix links
int sz = 1; // number of vertices, 0 is the rootThe function addString inserts the pattern into the trie. A character is treated as unsigned char so that its code is used as a non-negative index. If there is no transition by the character, a new vertex is created. At the vertex where the pattern ends, the flag is set.
void addString(const string &s)
{
int v = 0;
for (unsigned char c : s)
{
if (!go_[v][c]) go_[v][c] = sz++;
v = go_[v][c];
}
term[v] = true;
}The function buildAutomaton computes the suffix links and completes the transitions of the automaton using breadth-first search.
void buildAutomaton()
{
queue<int> q;Push the root of the trie (vertex number ) into the queue. The breadth-first search starts from it.
q.push(0);Extract a vertex from the queue. Its suffix link has already been computed, and the vertex was processed earlier, so the flag can immediately be supplemented with the flag of the vertex .
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 number of patterns , and then use the function getline to read the rest of the line containing .
cin >> n;
getline(cin, line); // read the rest of the line with the number nRead the patterns and insert the non-empty ones into the trie.
for (int i = 0; i < n; i++)
{
getline(cin, line);
if (!line.empty()) addString(line);
}Build the Aho — Corasick automaton.
buildAutomaton();Read the strings of the set until the end of the input. For each string we start at the root; the flag shows whether a pattern has been found in it.
while (getline(cin, line))
{
int v = 0;
bool found = false;Go through the characters of the string. Characters with codes and above are not represented in the automaton (by the statement, they do not occur in the input); if they appear, the automaton returns to the root. As soon as the automaton reaches a vertex with the flag , the string contains a pattern, and scanning the string stops.
for (unsigned char c : line)
{
v = go_[v][c];
if (term[v]) { found = true; break; }
}If a pattern is found, print the string.
if (found) cout << line << '\n';
}