Commitc2e90ab

authored

Fix a subscript error in the Prefix function page (#684)

Co-authored-by: iamspzero <li.zandeng@gmail.com>

1 parent841f81d commitc2e90abCopy full SHA for c2e90ab

File tree

-1

lines changed

-1

lines changed

Lines changed: 1 addition & 1 deletion

Original file line number	Diff line number	Diff line change
`@@ -63,7 +63,7 @@ To accomplish this, we have to use all the information computed in the previous`
`63`	`63`	`So let us compute the value of the prefix function $\pi$ for $i + 1$.`
`64`	`64`	`If $s[i+1] = s[\pi[i]]$, then we can say with certainty that $\pi[i+1] = \pi[i] + 1$, since we already know that the suffix at position $i$ of length $\pi[i]$ is equal to the prefix of length $\pi[i]$.`
`65`	`65`	`This is illustrated again with an example.`
`66`		`-$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}\_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 =s_i + 1}}\_{\pi[i+1] = \pi[i] + 1}$$`
	`66`	`+$$\underbrace{\overbrace{s_0 ~ s_1 ~ s_2}^{\pi[i]} ~ \overbrace{s_3}^{s_3 = s_{i+1}}}\_{\pi[i+1] = \pi[i] + 1} ~ \dots ~ \underbrace{\overbrace{s_{i-2} ~ s_{i-1} ~ s_{i}}^{\pi[i]} ~ \overbrace{s_{i+1}}^{s_3 =s_{i + 1}}}\_{\pi[i+1] = \pi[i] + 1}$$`
`67`	`67`
`68`	`68`	`If this is not the case, $s[i+1] \neq s[\pi[i]]$, then we need to try a shorter string.`
`69`	`69`	`In order to speed things up, we would like to immediately move to the longest length $j \lt \pi[i]$, such that the prefix property in the position $i$ holds, i.e. $s[0 \dots j-1] = s[i-j+1 \dots i]$:`

Comments

(0)