Content-Length: 260622 | pFad | http://github.com/cp-algorithms/cp-algorithms/commit/c098d8286bc3e78ab5294e4dfbf2395c6c1b2135

7E Update suffix-automaton.md · cp-algorithms/cp-algorithms@c098d82 · GitHub
Skip to content

Commit c098d82

Browse files
Oleksandr Kulkovadamant-pwn
authored andcommitted
Update suffix-automaton.md
1 parent 6b59f75 commit c098d82

File tree

1 file changed

+1
-1
lines changed

1 file changed

+1
-1
lines changed

src/string/suffix-automaton.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -596,7 +596,7 @@ $$cnt[link(v)] \text{ += } cnt[v]$$
596596
This gives the correct value for each state.
597597

598598
Why is this correct?
599-
The total states obtained not via cloning are exactly $length(T)$, and the first $i$ of them appeared when we added the first $i$ characters.
599+
The total number of states obtained _not_ via cloning is exactly $length(T)$, and the first $i$ of them appeared when we added the first $i$ characters.
600600
Consequently for each of these states we count the corresponding position at which it was processed.
601601
Therefore initially we have $cnt = 1$ for each such state, and $cnt = 0$ for all other.
602602

0 commit comments

Comments
 (0)








ApplySandwichStrip

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier!      Saves Data!


--- a PPN by Garber Painting Akron. With Image Size Reduction included!

Fetched URL: http://github.com/cp-algorithms/cp-algorithms/commit/c098d8286bc3e78ab5294e4dfbf2395c6c1b2135

Alternative Proxies:

Alternative Proxy

pFad Proxy

pFad v3 Proxy

pFad v4 Proxy