aho corasick text change

Mrityunjai Singh · Mrityunjai Singh · commit acc62aacb115 · 2025-04-16T01:26:37.000-07:00
diff --git a/src/string/aho_corasick.md b/src/string/aho_corasick.md
@@ -36,6 +36,7 @@ Accordingly, a trie for a set of strings is a trie such that each $\text{output}
 We now describe how to construct a trie for a given set of strings in linear time with respect to their total length.
 
 We introduce a structure for the vertices of the tree:
+
 ```{.cpp file=aho_corasick_trie_definition}
 const int K = 26;
 
@@ -209,7 +210,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(m \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(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.
 
 ## Applications
 
@@ -277,4 +278,5 @@ Thus we can find such a path  using depth first search (and if the search looks
 - [CodeChef - TWOSTRS](https://www.codechef.com/MAY20A/problems/TWOSTRS)
 
 ## References
+
 - [Stanford's CS166 - Aho-Corasick Automata](http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Slides02.pdf) ([Condensed](http://web.stanford.edu/class/archive/cs/cs166/cs166.1166/lectures/02/Small02.pdf))
