m -> n in Aho-Corasick

adamant-pwn · web-flow · commit 8c5bc69c3761 · 2025-04-18T23:47:45.000+02:00
diff --git a/src/string/aho_corasick.md b/src/string/aho_corasick.md
@@ -209,7 +209,7 @@ Assume that at the moment we stand in a vertex $v$ and consider a character $c$.
 1. $go[v][c] = -1$. In this case, we may assign $go[v][c] = go[u][c]$, which is already known by the induction hypothesis;
 2. $go[v][c] = w \neq -1$. In this case, we may assign $link[w] = go[u][c]$.
 
-In this way, we spend $O(1)$ time per each pair of a vertex and a character, making the running time $O(mk)$. The major overhead here is that we copy a lot of transitions from $u$ in the first case, while the transitions of the second case form the trie and sum up to $m$ over all vertices. To avoid the copying of $go[u][c]$, we may use a persistent array data structure, using which we initially copy $go[u]$ into $go[v]$ and then only update values for characters in which the transition would differ. This leads to the $O(n \log k)$ algorithm.
+In this way, we spend $O(1)$ time per each pair of a vertex and a character, making the running time $O(nk)$. The major overhead here is that we copy a lot of transitions from $u$ in the first case, while the transitions of the second case form the trie and sum up to $n$ over all vertices. To avoid the copying of $go[u][c]$, we may use a persistent array data structure, using which we initially copy $go[u]$ into $go[v]$ and then only update values for characters in which the transition would differ. This leads to the $O(n \log k)$ algorithm.
 
 ## Applications
 
