English version is in beta. All contents of the site should be already translated (mostly using machine translation), and everything should work properly. However, if you find any problems, please contact me.

Level 8A

To advance to the next level, you need to solve all problems.

Z-function

See the video recordings of lectures SIS.2008.B', section "Algorithms on strings".
Theory on e-maxx
Theory in wikipedia (!)
Theory on the ITMO website
Theory on habr

Problems on Z-function

Sqrt decomposition, aka root heuristics

Theory on e-maxx
Theory in ITMO notes
Article on habr
Mo algorithm (a bit different idea, but the basis is same)

Problems on sqrt decomposition

Sparse tables, binary ascent

Problems on sparse tables

algoprog.ru © Petr Kalinin, GNU AGPL, github.com/petr-kalinin/algoprog | About the license for the site materials | Blog (in Russian)