Aho–Corasick Automaton

Overview

The Aho–Corasick (AC) automaton is an automaton built on the structure of a Trie, incorporating the ideas of KMP, and is used for tasks such as multi-pattern matching.

An AC automaton is, in essence, an automaton built on a Trie.

Before reading this article, please read KMP and Trie.

Explanation

Simply put, building an AC automaton consists of two steps:

1. The basic Trie structure: construct a Trie from all the pattern strings;
2. The idea of KMP: construct failure pointers for all nodes in the Trie.

Once construction is complete, the automaton can be used for multi-pattern matching.

Building the Trie

Initially, the AC automaton inserts several pattern strings into a Trie, and then builds the AC automaton on that Trie. This Trie is an ordinary Trie, so it can be built using the standard Trie construction method.

Note that nodes in the Trie represent prefixes of pattern strings. We will also call them states below. A node represents a state, and a Trie edge is a state transition.

Formally, for several pattern strings $s_1,s_2,\cdots,s_n$, let the set of all states after constructing their Trie be denoted by $Q$.

Failure Pointers

The AC automaton uses a fail pointer to assist in matching multiple pattern strings.

The fail pointer of state $u$ points to another state $v$, where $v\in Q$ and $v$ is the longest suffix of $u$ (that is, among the suffix states, the longest one is chosen as the fail pointer).

Compared with the next pointer in KMP, the fail pointer has the following properties:

1. Similarity: both are pointers used to jump when a mismatch occurs.
2. Difference: the next pointer finds the longest Border (that is, the longest equal prefix and suffix), whereas the fail pointer points to the longest suffix matching the current state among the prefixes of all pattern strings.

KMP matches only one pattern string, whereas the AC automaton matches multiple pattern strings. The node pointed to by a fail pointer may correspond to another pattern string, whose prefix is different.

In summary, the failure pointer of an AC automaton points to the longest suffix state of the current state.

Note: when an AC automaton performs matching, multiple pattern strings may match at the same position.

Building the Pointers

The basic idea for constructing fail pointers is introduced below:

The construction of fail pointers can follow the idea of constructing the next pointer in KMP.

Consider the current node $u$ in the Trie. Let the parent of $u$ be $p$, and let $p$ point to $u$ through the edge labeled $c$, namely $\operatorname{trie}(p, c)=u$. Assume that the fail pointers of all nodes whose depth is less than that of $u$ have already been found.

1. If $\operatorname{trie}(\operatorname{fail}(p), c)$ exists, let the fail pointer of $u$ point to $\operatorname{trie}(\operatorname{fail}(p), c)$. This is equivalent to appending the character $c$ after $p$ and $\operatorname{fail}(p)$, which correspond to $u$ and $\operatorname{fail}(u)$, respectively;
2. If $\operatorname{trie}(\operatorname{fail}(p), c)$ does not exist, continue by finding $\operatorname{trie}(\operatorname{fail}(\operatorname{fail}(p)), c)$. Repeat this check, following fail pointers until reaching the root;
3. If it still does not exist, let the fail pointer point to the root.

This completes the construction of $\operatorname{fail}(u)$.

Example

The following GIFs demonstrate the process of constructing fail pointers for the Trie formed by the strings $\mathtt{i}$、$\mathtt{he}$、$\mathtt{his}$、$\mathtt{she}$、and $\mathtt{hers}$:

1. Yellow node: the current node $u$.
2. Green node: a node whose BFS traversal has been completed.
3. Orange edge: a fail pointer.
4. Red edge: the fail pointer currently being found.

We focus on constructing the fail pointer of node $6$:

Find the parent of $6$, node $5$, with $\operatorname{fail}(5)=10$. However, node $10$ has no edge labeled $\mathtt{s}$; continue following the fail pointer of $10$, obtaining $\operatorname{fail}(10)=0$. Node $0$ has an edge labeled $\mathtt{s}$, pointing to node $7$, so $\operatorname{fail}(6)=7$.

The completed state is shown below:

Trie and Dictionary Graph

Consider the build function. It has two goals: constructing fail pointers and constructing the automaton. The relevant variables are defined as follows:

1. tr[u].son[c]: there are two ways to understand this. It can simply be viewed as an edge in the Trie, namely $\operatorname{trie}(u, c)$; or it can be viewed as the state (node) reached by appending character $c$ after state (node) $u$, namely a state transition function $\operatorname{trans}(u, c)$. For convenience, we use the second interpretation below.
2. The queue q: used for BFS traversal of the Trie.
3. tr[u].fail: the fail pointer of node $u$.

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) q.push(tr[0].son[i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

def build():
    for i in range(0, 26):
        if tr[0][i] != 0:
            q.append(tr[0][i])
    while q:
        u = q.pop(0)
        for i in range(0, 26):
            if tr[u][i] != 0:
                fail[tr[u][i]] = tr[fail[u]][i]
                q.append(tr[u][i])
            else:
                tr[u][i] = tr[fail[u]][i]

Explanation

The build function enqueues nodes in BFS order and finds their fail pointers one by one. Here the root of the Trie is node $0$, so we enqueue the children of the root one by one. If the root itself were enqueued, the first BFS step would mark the fail pointer of each child of the root as the child itself. Therefore, we enqueue the children of the root individually instead of enqueuing the root.

We then begin BFS. Each time, we remove the first node $u$ from the queue ($\operatorname{fail}(u)$ was found during an earlier BFS step), and then traverse the character set (here $0 \sim 25$, corresponding to $\mathtt{a} \sim \mathtt{z}$, namely all children of $u$):

1. If $\operatorname{trans}(u, c)$ exists, assign the fail pointer of $\operatorname{trans}(u, c)$ to $\operatorname{trans}(\operatorname{fail}(u), c)$. According to the description above, we should use a while loop to keep following fail pointers and check whether the node corresponding to character $c$ exists before assigning it. Here, however, the code is simplified through special handling, which will be explained below;
2. Otherwise, let $\operatorname{trans}(u, c)$ point to the state $\operatorname{trans}(\operatorname{fail}(u), c)$.

The handling here modifies the Trie structure through the code in the else statement, linking nonexistent Trie states to the corresponding state of the failure pointer. In the original Trie, each node represents a string $S$, which is a prefix of some pattern string. After modifying the Trie structure, although many transition relationships have been added, the string represented by each node (state) remains unchanged.

Meanwhile, $\operatorname{trans}(S, c)$ is equivalent to appending character $c$ after $S$ to form another state $S'$. If $S'$ exists, then some pattern string has $S'$ as a prefix; otherwise, we let $\operatorname{trans}(S, c)$ point to $\operatorname{trans}(\operatorname{fail}(S), c)$. Since the string corresponding to $\operatorname{fail}(S)$ is a suffix of $S$, the string corresponding to $\operatorname{trans}(\operatorname{fail}(S), c)$ is also a suffix of $S'$.

In other words, when traversing the Trie, we only move from $S$ to $S'$, which is equivalent to matching an $S'$. When traversing the AC automaton, we move from $S$ to a suffix of $S'$. In other words, we match one character $c$ and then discard part of the prefix of $S$. Discarding the prefix is clearly valid. At the same time, if the text string can match $S$, it can clearly also match a suffix of $S$, so the fail pointer likewise discards a prefix. The fail pointer is, in fact, a set of suffixes of $S$.

There is another relatively simple way to understand the son child array of a Trie node: if a mismatch occurs at position $u$, we jump to position $\operatorname{fail}(u)$. Note that this may require following the fail array multiple times before reaching the next position that can match. Therefore, we can use son to record the next position that can match directly, ensuring the time complexity of the program.

The modification to the Trie structure here makes matching transitions more complete. At the same time, it compresses the paths of fail pointer jumps, turning what originally required many fail jumps into one jump.

Process

Here, several GIFs again illustrate the construction process:

1. Blue node: the node $u$ reached by the BFS traversal.
2. Blue edge: an edge added by the AC automaton's modification of the Trie structure under the current node.
3. Black edge: an edge added by the AC automaton's modification of the Trie structure.
4. Red edge: the fail pointer found for the current node.
5. Yellow edge: a fail pointer.
6. Gray edge: a Trie edge.

It can be seen that the many interwoven black edges turn the Trie into a dictionary graph. The black edges leading to the root are omitted from the figure (otherwise it would be even more cluttered). We focus on what happens while traversing node $5$. We find the fail pointer of $\operatorname{trans}(5, \mathtt{s})=6$:

The original strategy is to follow the fail pointer. We jump to $\operatorname{fail}(5)=10$ and find no Trie edge labeled $\mathtt{s}$, so we jump to $\operatorname{fail}(10)=0$, where we find $\operatorname{trie}(0, \mathtt{s})=7$; thus $\operatorname{fail}(6)=7$. With the black and blue edges, however, after jumping to $\operatorname{fail}(5)=10$, we can directly follow $\operatorname{trans}(10, \mathtt{s})=7$ to reach node $7$.

These are the two things completed by build: constructing fail pointers and building the dictionary graph. This dictionary graph also plays a key role during queries.

Multi-pattern Matching

Next, let us analyze the query function:

int query(const char t[]) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    for (int j = u; j && tr[j].cnt != -1; j = tr[j].fail) {
      res += tr[j].cnt, tr[j].cnt = -1;
    }
  }
  return res;
}

def query(t: str) -> int:
    u, res = 0, 0
    for c in t:
        u = tr[u][c - ord("a")]
        j = u
        while j and e[j] != -1:
            res += e[j]
            e[j] = -1
            j = fail[j]
    return res

Explanation

Here $u$ is the node currently matched in the Trie, and res is the returned answer. We traverse the matching string character by character, with $u$ tracking the current character in the Trie. We use the fail pointer to find all matching pattern strings and add them to the answer. We then set the occurrence count of each matched string to zero, so the same string is not counted again. As analyzed above, the structure of the Trie is essentially a trans function, and once this function has been built, we discard some prefixes to reach the minimum match while matching the string. The fail pointer points to more matching states. Finally, here is one last figure. For the automaton just discussed:

Starting from the root, we try to match $\mathtt{ushersheishis}$, so the changes in $p$ are as follows:

1. Red node: the $p$ node.
2. Pink arrow: the jump of $p$ in the automaton.
3. Blue edge: a successfully matched pattern string.
4. Blue node: the node (state) reached while following a fail pointer.

Efficiency Optimization

For the problem, see Luogu P5357: AC Automaton Template.

In our AC automaton, every match repeatedly follows fail edges to find all matches. This is relatively inefficient and may time out on some problems.

How can this be optimized? First, observe a property of fail pointers: in an AC automaton, if only the fail edges are retained, the remaining graph is necessarily a tree.

This is obvious because fail cannot form a cycle, and its depth is always smaller than the current depth.

Thus, matching in an AC automaton can be transformed into a path-sum problem on the fail tree; we only need to optimize this part.

Two approaches are provided here.

Topological-sort Optimization

Observe that most of the time is wasted following fail on every match. If we record the values in advance and sum them all at once at the end, the efficiency can be improved.

Therefore, by performing a topological sort on the inward tree of the fail tree, we can calculate the occurrence count of every pattern string at once.

The build function is extended with indegree statistics to prepare for the topological sort.

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) q.push(tr[0].son[i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        tr[tr[tr[u].fail].son[i]].du++;  // indegree count
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

Then, when querying, we only mark the ans of the node we reach, and use topological sorting at the end to obtain the answers.

void query(const char t[]) {
  int u = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    tr[u].ans++;
  }
}

void topu() {
  queue<int> q;
  for (int i = 0; i <= tot; i++)
    if (tr[i].du == 0) q.push(i);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ans[tr[u].idx] = tr[u].ans;
    int v = tr[u].fail;
    tr[v].ans += tr[u].ans;
    if (!--tr[v].du) q.push(v);
  }
}

Finally, the main function:

int main() {
  // do_something();
  AC::build();
  scanf("%s", s + 1);
  AC::query(s);
  AC::topu();
  for (int i = 1; i <= n; i++) printf("%d\n", AC::ans[idx[i]]);
  // do_another_thing();
}

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

constexpr int N = 2e5 + 6;
constexpr int LEN = 2e6 + 6;
constexpr int SIZE = 2e5 + 6;

int n;

namespace AC {
struct Node {
  int son[26];  // child nodes
  int ans;      // match count
  int fail;     // fail pointer
  int du;       // indegree
  int idx;

  void init() {  // initialize the node
    memset(son, 0, sizeof(son));
    ans = fail = idx = 0;
  }
} tr[SIZE];

int tot;  // total number of nodes
int ans[N], pidx;

void init() {
  tot = pidx = 0;
  tr[0].init();
}

void insert(char s[], int &idx) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    int &son = tr[u].son[s[i] - 'a'];  // reference to the next child node
    if (!son) son = ++tot, tr[son].init();  // insert and initialize a new node if absent
    u = son;                                // continue from the next node
  }
  // Identical pattern strings may occur, so map identical strings to the same number
  if (!tr[u].idx) tr[u].idx = ++pidx;  // first occurrence: assign a new number
  idx = tr[u].idx;  // the number of this pattern string corresponds to this node's number
}

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) q.push(tr[0].son[i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {                               // corresponding child exists
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];  // follow only one fail pointer
        tr[tr[tr[u].fail].son[i]].du++;                 // indegree count
        q.push(tr[u].son[i]);                           // add it to the queue
      } else
        tr[u].son[i] =
            tr[tr[u].fail]
                .son[i];  // link a nonexistent Trie state to the corresponding state of the failure pointer
    }
  }
}

void query(char t[]) {
  int u = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];  // transition
    tr[u].ans++;
  }
}

void topu() {
  queue<int> q;
  for (int i = 0; i <= tot; i++)
    if (tr[i].du == 0) q.push(i);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    ans[tr[u].idx] = tr[u].ans;
    int v = tr[u].fail;
    tr[v].ans += tr[u].ans;
    if (!--tr[v].du) q.push(v);
  }
}
}  // namespace AC

char s[LEN];
int idx[N];

int main() {
  AC::init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    AC::insert(s, idx[i]);
    AC::ans[i] = 0;
  }
  AC::build();
  scanf("%s", s + 1);
  AC::query(s);
  AC::topu();
  for (int i = 1; i <= n; i++) {
    printf("%d\n", AC::ans[idx[i]]);
  }
  return 0;
}

DFS Optimization

The idea is similar to topological sorting, except that we use DFS instead. In fact, the two methods are essentially the same: both sum the subtrees of the fail tree.

For the complete code, see summary template 3.

DP on an AC Automaton

This section uses P2292 [HNOI2004] L Language as an example.

A straightforward idea is easy to find: build an AC automaton, perform transitions for all substrings along the fail pointers on the AC automaton, and finally take the maximum to obtain the answer.

The main code is as follows. If you are unfamiliar with the type definitions in the code, you can first look at the complete code at the end:

int query(const char t[]) {
  int u = 0, len = strlen(t + 1);
  for (int i = 1; i <= len; i++) dp[i] = 0;
  for (int i = 1; i <= len; i++) {
    u = tr[u].son[t[i] - 'a'];
    for (int j = u; j; j = tr[j].fail) {
      if (tr[j].idx && (dp[i - tr[j].depth] || i - tr[j].depth == 0)) {
        dp[i] = dp[i - tr[j].depth] + tr[j].depth;
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= len; i++) ans = std::max(ans, dp[i]);
  return ans;
}

However, the complexity of this approach is not linear (because it follows the fail pointer of every node), so it will time out on the second subtask and needs to be optimized.

Now consider the special properties of the problem. We find that all word lengths are only $20$, so state-compression optimization comes to mind.

The current bottleneck is mainly following fail. If this step can be optimized to $O(1)$, the entire problem can be solved in strictly linear time.

We can record the possible substring lengths among the first $20$ letters and compress them into a state, storing that state in every child node.

Then build can be written as follows:

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) {
      q.push(tr[0].son[i]);
      tr[tr[0].son[i]].depth = 1;
    }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    int v = tr[u].fail;
    // update the state here
    tr[u].stat = tr[v].stat;
    if (tr[u].idx) tr[u].stat |= 1 << tr[u].depth;
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        tr[tr[u].son[i]].depth = tr[u].depth + 1;  // record the depth
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

Then the loop that follows fail can be removed from the query, simplifying the code as follows:

int query(const char t[]) {
  int u = 0, mx = 0;
  unsigned st = 1;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    st <<= 1;  // each step down increases every length by 1
    if (tr[u].stat & st) st |= 1, mx = i;
  }
  return mx;
}

Our tr[u].stat maintains the set of lengths along the entire fail chain starting from node $u$ (the set of lengths is less than $32$, so this causes no problem), while st maintains the set of lengths among the first $32$ positions of the query string (because of natural state-compression overflow).

If the result of the & operation is not $0$, the intersection of the two length sets is nonempty, so a match has been found.

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

constexpr int N = 20 + 6, M = 50 + 6;
constexpr int LEN = 2e6 + 6;
constexpr int SIZE = 450 + 6;

int n, m;

namespace AC {
struct Node {
  int son[26];
  int fail;
  int idx;
  int depth;
  unsigned stat;

  void init() {
    memset(son, 0, sizeof(son));
    fail = idx = depth = 0;
  }
} tr[SIZE];

int tot;

void init() {
  tot = 0;
  tr[0].init();
}

void insert(char s[], int idx) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    int &son = tr[u].son[s[i] - 'a'];
    if (!son) son = ++tot, tr[son].init();
    u = son;
  }
  tr[u].idx = idx;
}

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) {
      q.push(tr[0].son[i]);
      tr[tr[0].son[i]].depth = 1;
    }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    int v = tr[u].fail;
    // update the state here
    tr[u].stat = tr[v].stat;
    if (tr[u].idx) tr[u].stat |= 1 << tr[u].depth;
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        tr[tr[u].son[i]].depth = tr[u].depth + 1;  // record the depth
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

int query(char t[]) {
  int u = 0, mx = 0;
  unsigned st = 1;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    st <<= 1;
    if (tr[u].stat & st) st |= 1, mx = i;
  }
  return mx;
}
}  // namespace AC

char s[LEN];

int main() {
  AC::init();
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    AC::insert(s, i);
  }
  AC::build();
  for (int i = 1; i <= m; i++) {
    scanf("%s", s + 1);
    printf("%d\n", AC::query(s));
  }
  return 0;
}

Summary

Time complexity: let $|s_i|$ be the length of a pattern string, $|S|$ be the length of the text string, and $|\Sigma|$ be the size of the character set (a constant, generally $26$). If the Trie graph is connected, the time complexity is $O(\sum|s_i|+n|\Sigma|+|S|)$, where $n$ is the number of nodes in the AC automaton and can be as large as $O(\sum|s_i|)$. If the Trie graph is not connected, and empty children are avoided during construction of the fail pointers, the time complexity is $O(\sum|s_i|+|S|)$.

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

constexpr int N = 1e6 + 6;
constexpr int LEN = 1e6 + 6;
constexpr int SIZE = 1e6 + 6;

int n;

namespace AC {
struct Node {
  int son[26];  // child nodes
  int cnt;      // number of strings ending at this node
  int fail;     // fail pointer

  void init() {  // initialize the node
    memset(son, 0, sizeof(son));
    cnt = fail = 0;
  }
} tr[SIZE];

int tot;  // total number of nodes

void init() {
  tot = 0;
  tr[0].init();
}

void insert(char s[]) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    int &son = tr[u].son[s[i] - 'a'];  // reference to the next child node
    if (!son) son = ++tot, tr[son].init();  // insert and initialize a new node if absent
    u = son;                                // continue from the next node
  }
  tr[u].cnt++;
}

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) q.push(tr[0].son[i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {                               // corresponding child exists
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];  // follow only one fail pointer
        q.push(tr[u].son[i]);                           // add it to the queue
      } else
        tr[u].son[i] =
            tr[tr[u].fail]
                .son[i];  // link a nonexistent Trie state to the corresponding state of the failure pointer
    }
  }
}

int query(char t[]) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];  // transition
    for (int j = u; j && tr[j].cnt != -1; j = tr[j].fail) {
      res += tr[j].cnt, tr[j].cnt = -1;
    }
  }
  return res;
}
}  // namespace AC

char s[LEN];

int main() {
  AC::init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    AC::insert(s);
  }
  AC::build();
  scanf("%s", s + 1);
  printf("%d", AC::query(s));
  return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;

constexpr int N = 150 + 6;
constexpr int LEN = 1e6 + 6;
constexpr int SIZE = N * 70 + 6;

int n;

namespace AC {
struct Node {
  int son[26];
  int fail;
  int idx;

  void init() {
    memset(son, 0, sizeof(son));
    idx = fail = 0;
  }
} tr[SIZE];

int tot;

void init() {
  tot = 0;
  tr[0].init();
}

void insert(char s[], int idx) {  // insert string s with index idx
  int u = 0;
  for (int i = 1; s[i]; i++) {
    int &son = tr[u].son[s[i] - 'a'];
    if (!son) son = ++tot, tr[son].init();
    u = son;
  }
  tr[u].idx = idx;
}

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) q.push(tr[0].son[i]);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

int query(char t[], int cnt[]) {
  int u = 0, res = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    for (int j = u; j; j = tr[j].fail)
      ++cnt[tr[j].idx];  // count the occurrences of each string
  }
  for (int i = 0; i <= tot; ++i)
    if (tr[i].idx) res = max(res, cnt[tr[i].idx]);
  return res;
}
}  // namespace AC

char s[N][75], t[LEN];
int cnt[N];  // number of occurrences of each string

int main() {
  while (scanf("%d", &n) != EOF && n != 0) {
    AC::init();
    for (int i = 1; i <= n; i++) {
      scanf("%s", s[i] + 1);
      AC::insert(s[i], i);
      cnt[i] = 0;
    }
    AC::build();
    scanf("%s", t + 1);
    int x = AC::query(t, cnt);
    printf("%d\n", x);
    for (int i = 1; i <= n; i++)
      if (cnt[i] == x) printf("%s\n", s[i] + 1);
  }
  return 0;
}

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

constexpr int N = 2e5 + 6;
constexpr int LEN = 2e6 + 6;
constexpr int SIZE = 2e5 + 6;

int n;

namespace AC {
struct Node {
  int son[26];
  int ans;
  int fail;
  int idx;

  void init() {
    memset(son, 0, sizeof(son));
    ans = idx = 0;
  }
} tr[SIZE];

int tot;
int ans[N], pidx;

vector<int> g[SIZE];  // fail tree

void init() {
  tot = pidx = 0;
  tr[0].init();
}

void insert(char s[], int &idx) {
  int u = 0;
  for (int i = 1; s[i]; i++) {
    int &son = tr[u].son[s[i] - 'a'];
    if (!son) son = ++tot, tr[son].init();
    u = son;
  }
  // Identical pattern strings may occur, so map identical strings to the same number
  if (!tr[u].idx) tr[u].idx = ++pidx;  // first occurrence: assign a new number
  idx = tr[u].idx;  // the number of this pattern string corresponds to this node's number
}

void build() {
  queue<int> q;
  for (int i = 0; i < 26; i++)
    if (tr[0].son[i]) {
      q.push(tr[0].son[i]);
      g[0].push_back(tr[0].son[i]);  // do not forget this fail edge
    }
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < 26; i++) {
      if (tr[u].son[i]) {
        tr[tr[u].son[i]].fail = tr[tr[u].fail].son[i];
        g[tr[tr[u].fail].son[i]].push_back(tr[u].son[i]);  // record the fail tree
        q.push(tr[u].son[i]);
      } else
        tr[u].son[i] = tr[tr[u].fail].son[i];
    }
  }
}

void query(char t[]) {
  int u = 0;
  for (int i = 1; t[i]; i++) {
    u = tr[u].son[t[i] - 'a'];
    tr[u].ans++;
  }
}

void dfs(int u) {
  for (int v : g[u]) {
    dfs(v);
    tr[u].ans += tr[v].ans;
  }
  ans[tr[u].idx] = tr[u].ans;
}
}  // namespace AC

char s[LEN];
int idx[N];

int main() {
  AC::init();
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%s", s + 1);
    AC::insert(s, idx[i]);
    AC::ans[i] = 0;
  }
  AC::build();
  scanf("%s", s + 1);
  AC::query(s);
  AC::dfs(0);
  for (int i = 1; i <= n; i++) {
    printf("%d\n", AC::ans[idx[i]]);
  }
  return 0;
}