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.

Knuth-Morris-Pratt Algorithm (KMP)

See the video recordings of lectures SIS.2008.B', section "Algorithms on strings".
Theory on e-maxx
Theory on habr
You can search the Internet for more.
In addition to actually searching for a substring in a string, the prefix function itself also often has other useful uses. There are also tasks for this below.
Some of the tasks below were previously in hash tasks. Solve them once again, this time using the CMP.

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