{"id":337283,"date":"2022-08-19T15:00:41","date_gmt":"2022-08-19T15:00:41","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=337283"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=337283","title":{"rendered":"<span>\u0421\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e \u043d\u0430 python<\/span>"},"content":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0421\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e  (Suffix Tree, ST)  \u2013 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445,  \u043a\u043e\u0442\u043e\u0440\u0430\u044f  \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 &#171;\u043f\u0440\u043e\u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c&#187; \u0441\u0442\u0440\u043e\u043a\u0443 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0442 \u0435\u0451 \u0434\u043b\u0438\u043d\u044b, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0442\u043e\u043c \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 (\u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u041e(\u0434\u043b\u0438\u043d\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438)).<\/p>\n<p>\u0422\u0435\u043c\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u0438 \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f  \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u0430 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree\" rel=\"noopener noreferrer nofollow\">\u0432\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a>, <a href=\"https:\/\/habr.com\/ru\/post\/258121\/\" rel=\"noopener noreferrer nofollow\">\u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0412\u0435\u0439\u043d\u0435\u0440\u0430, \u044f\u0437\u044b\u043a \u0421\u0438<\/a>, \u0438 <a href=\"https:\/\/habr.com\/ru\/post\/533774\/\" rel=\"noopener noreferrer nofollow\">\u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c  \u0423\u043a\u043a\u043e\u043d\u0435\u043d\u0430<\/a>).<br \/>\u041d\u043e \u0432\u0441\u0435\u0433\u0434\u0430 \u0435\u0441\u0442\u044c \u0441\u043e\u0431\u043b\u0430\u0437\u043d \u043f\u043e\u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u0438 &#171;\u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e\u0449\u0435 \u0438 \u044f\u0441\u043d\u0435\u0435&#187;, \u0445\u043e\u0442\u044f \u0448\u0430\u043d\u0441\u043e\u0432 \u043c\u0430\u043b\u043e. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0440\u0438\u0441\u043a\u043d\u0443.<\/p>\n<p>\u0421\u043e\u0431\u043b\u0430\u0437\u043d \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432 \u0441\u0432\u044f\u0437\u0438 \u0441\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c\u0438 \u043c\u043e\u043c\u0435\u043d\u0442\u0430\u043c\u0438:<\/p>\n<ul>\n<li>\n<p>\u0412 \u043d\u0430\u0441\u0442\u0443\u043f\u0438\u0432\u0448\u0435\u043c \u043c\u0438\u0440\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u043e\u0432\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043a\u0430\u043a \u0431\u044b \u043c\u044b \u0436\u0438\u043b\u0438 \u0431\u0435\u0437 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0445\u043e\u0436\u0438\u0445 \u043a\u0443\u0441\u043e\u0447\u043a\u043e\u0432 \u0432 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 (\u043f\u043e\u0438\u0441\u043a \u0441\u0442\u0440\u043e\u043a \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445, \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0430 \u0414\u041d\u041a,  \u0430\u043d\u0442\u0438\u043f\u043b\u0430\u0433\u0438\u0430\u0442, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441\u0436\u0430\u0442\u0438\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0432\u044b\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0438 \u0434\u0440.). Suffix Tree \u0438 Suffix Array \u2013 \u0433\u043b\u0430\u0432\u043d\u044b\u0435  \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u0441\u0435 \u044d\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<\/li>\n<li>\n<p>ST \u043f\u043e \u043f\u0440\u0430\u0432\u0443 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445. \u0415\u0441\u043b\u0438 \u0432 \u0438\u043d\u0441\u0442\u0438\u0442\u0443\u0442\u0435 \u043d\u0430 \u044d\u043a\u0437\u0430\u043c\u0435\u043d\u0435 \u0432\u0430\u0441 \u0441\u043f\u0440\u0430\u0448\u0438\u0432\u0430\u044e\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST, \u0435\u0441\u0442\u044c \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u044b\u0435 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0432\u0430\u0441 \u0432\u0430\u043b\u044f\u0442.<\/p>\n<\/li>\n<li>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u0443\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 35 \u0441\u0442\u0440\u043e\u043a \u043d\u0430 python (\u0441\u043c. \u043d\u0438\u0436\u0435 \u043c\u0435\u0442\u043e\u0434 _build_tree). \u0418\u0445 \u0431\u0443\u043a\u0432\u0430\u043b\u044c\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0443\u0447\u0438\u0442\u044c \u0438 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u043a\u0430\u043a \u043d\u0435\u043a\u043e\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0430, \u043a\u0430\u043a \u0432\u043e\u043f\u043b\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432 \u043d\u0430\u0431\u043e\u0440 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0442\u0440\u0443\u0434 \u0447\u0435\u043b\u043e\u0432\u0435\u0447\u0435\u0441\u043a\u043e\u0439 \u043c\u044b\u0441\u043b\u0438, \u043f\u0440\u0438\u0447\u0451\u043c \u043d\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u0430, \u0438 \u043f\u0435\u0440\u0432\u044b\u0435 \u0438\u0437 \u043d\u0438\u0445 \u0442\u043e\u0447\u043d\u043e \u0433\u0435\u043d\u0438\u0438. \ud83d\ude42 \u0415\u0441\u0442\u044c \u0441\u043e\u0431\u043b\u0430\u0437\u043d, \u0432\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044f\u0441\u044c \u0432 \u043a\u043e\u0434, \u043f\u0440\u0438\u043a\u043e\u0441\u043d\u0443\u0442\u044c\u0441\u044f \u043a \u0432\u0435\u043b\u0438\u043a\u043e\u043c\u0443 \u0438 \u0447\u0435\u043c\u0443-\u0442\u043e \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0435\u0440\u0432\u044b\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a 1973  \u0433\u043e\u0434\u0443, \u043d\u043e \u043d\u043e\u0432\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u043b\u0438 \u0432\u0441\u0451 \u044d\u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u044f\u0432\u043b\u044f\u0442\u044c\u0441\u044f:<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree#CITEREFWeiner1973\" rel=\"noopener noreferrer nofollow\">Weiner<\/a>, 1973 \u2013 \u043f\u0435\u0440\u0432\u044b\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u043e\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u0435\u0440\u0432\u043e\u043c\u0443.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Ukkonen%27s_algorithm\" rel=\"noopener noreferrer nofollow\">Ukkonen&#8217;s algorithm<\/a>, 1995 \u2013 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c\u0443,  \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u043e\u043d\u043b\u0430\u0439\u043d (\u043a\u043e\u0433\u0434\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0431\u0435\u0440\u0443\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0437 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043a\u0430).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree#CITEREFFarach1997\" rel=\"noopener noreferrer nofollow\">Farach<\/a>, 1997 \u2013 Optimal suffix tree construction with large alphabets \u2013 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u043e\u0432 \u043b\u044e\u0431\u043e\u0439 \u0434\u043b\u0438\u043d\u044b (\u0432 \u043e\u0446\u0435\u043d\u043a\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u043b\u0438\u043d\u0430 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/core.ac.uk\/download\/pdf\/82790401.pdf\" rel=\"noopener noreferrer nofollow\">Dany Breslauer, Giuseppe F. Italiano<\/a>,  2011 \u2013 Near real-time suffix tree construction \u2013 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043e\u043d\u043b\u0430\u0439\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c Ukkonen&#8217;s algorithm, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n \\log\\log  n)\" alt=\"O(n \\log\\log  n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/78a\/7c2\/dd0\/78a7c2dd04ce9ded678a82201e233670.svg\" width=\"113\" height=\"22\"\/>\u0432\u043c\u0435\u0441\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0cc\/680\/d78\/0cc680d783f637e8539bde95d75670f3.svg\" width=\"42\" height=\"22\"\/>, \u0433\u0434\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6b0\/f41\/4a5\/6b0f414a5a44b40ff065f648eeb94e60.svg\" width=\"12\" height=\"12\"\/> \u2013 \u0434\u043b\u0438\u043d\u0430  \u0442\u0435\u043a\u0441\u0442\u0430, \u043d\u043e \u0437\u0430\u0442\u043e \u0438 \u0441\u0440\u0435\u0434\u043d\u0435\u0435, \u0438 \u0445\u0443\u0434\u0448\u0435\u0435 \u0445\u0443\u0434\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0440\u0430\u0432\u043d\u043e<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(\\log\\log  n)\" alt=\"O(\\log\\log  n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/811\/a8d\/8bf\/811a8d8bfe058d1e7842f55c95472476.svg\" width=\"98\" height=\"22\"\/>, \u0430 \u0443 Ukkonen&#8217;s algorithm \u043d\u0430 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043c\u043e\u0436\u0435\u0442 \u0443\u0439\u0442\u0438 \u0432\u0440\u0435\u043c\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0cc\/680\/d78\/0cc680d783f637e8539bde95d75670f3.svg\" width=\"42\" height=\"22\"\/>.<\/p>\n<\/li>\n<\/ul>\n<h2>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/h2>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u0442\u0435\u043a\u0441\u0442 &#171;abrakadabra&#187;.<\/p>\n<p>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u044d\u0442\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430 \u2013 \u044d\u0442\u043e \u0441\u0442\u0440\u043e\u043a\u0438<\/p>\n<p><code>abrakadabra<br \/>brakadabra<br \/>rakadabra<br \/>akadabra<br \/>kadabra<br \/>adabra<br \/>dabra<br \/>abra<br \/>bra<br \/>ra<br \/>a<\/code><\/p>\n<p>\u0418\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0438\u0437\u043e\u0448\u043b\u043e <strong>\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e &#171;\u0441\u043a\u043b\u0435\u0435\u043a&#187; \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0441\u0442\u0440\u043e\u043a \u043f\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c<\/strong>:<\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a<\/p>\n<p><code>abrakadabra<br \/>abra<br \/>adabra<br \/>akadabra<br \/>a<br \/>brakadabra<br \/>bra<br \/>rakadabra<br \/>ra<br \/>kadabra<br \/>dabra<\/code><\/p>\n<details class=\"spoiler\">\n<summary>\u0414\u043b\u044f &#171;\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u043a\u043b\u0435\u0439\u043a\u0438&#187; \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0443 <\/summary>\n<div class=\"spoiler__content\">\n<p>\u041a\u0441\u0442\u0430\u0442\u0438, \u044d\u0442\u043e\u0442 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0438 \u0435\u0441\u0442\u044c Suffix Array):<code><br \/>a<br \/>adabra<br \/>abra<br \/>abrakadabra<br \/>akadabra<br \/>bra<br \/>brakadabra<br \/>dabra<br \/>kadabra<br \/>ra<br \/>rakadabra<\/code><\/p>\n<\/div>\n<\/details>\n<p>\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 <strong>\u0441\u043a\u043b\u0435\u0439\u043a\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432<\/strong> \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<figure class=\"\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/33f\/596\/1be\/33f5961beca109c71ce12bc05b003bb0.png\" width=\"442\" height=\"369\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/33f\/596\/1be\/33f5961beca109c71ce12bc05b003bb0.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e: \u0434\u0435\u0440\u0435\u0432\u043e, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u2013 \u043a\u043e\u0440\u0435\u043d\u044c (\u0441\u0430\u043c\u0430\u044f \u043b\u0435\u0432\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430), \u0438 \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430 \u0440\u0451\u0431\u0440\u0430\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430. \u041b\u044e\u0431\u043e\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u043a\u0430\u043a\u043e\u0439-\u043b\u0438\u0431\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435\u043c \u0441\u0442\u0440\u043e\u043a, \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b\u0445 \u043d\u0430 \u0440\u0451\u0431\u0440\u0430\u0445.\u00a0<strong>\u041b\u044e\u0431\u043e\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u043e\u0436\u043d\u043e &#171;\u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c&#187; \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430<\/strong>\u00a0\u0438 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435. \u041d\u043e \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u043d\u0435 \u0432\u0441\u0435 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043a\u0430\u043a\u043e\u043c\u0443-\u0442\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0443, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043f\u043e\u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u0430\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u0432\u0435\u0442\u0432\u0438\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b. \u041d\u0430 \u044d\u0442\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u0442\u0430\u043a\u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0435\u0442. \u041d\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f &#171;abac&#187;. \u0412 \u043d\u0451\u043c \u0431\u0443\u0434\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0435 &#171;a&#187;, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p>\u041f\u0443\u0442\u0438 &#171;ra-kadabra&#187; \u0438 &#171;bra-kadabra&#187; \u043c\u043e\u0436\u043d\u043e \u043a\u0430\u0436\u0434\u044b\u0439 &#171;\u0441\u0445\u043b\u043e\u043f\u043d\u0443\u0442\u044c&#187; \u0432 \u043e\u0434\u043d\u043e \u0440\u0435\u0431\u0440\u043e, \u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0432\u043d\u0443\u0442\u0440\u0438 \u0440\u0435\u0431\u0440\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441. <\/p>\n<p>\u0415\u0441\u0442\u044c <a href=\"https:\/\/brenden.github.io\/ukkonen-animation\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/a>  \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 &#171;\u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c\u0443&#187;,  \u043e\u043d\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0430\u0438\u0432\u043d\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u0438\u043d\u044b.<\/p>\n<h2>\u041d\u0430\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>\u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0431\u0435 \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b \u2013 \u043a\u043e\u0440\u0435\u043d\u044c. \u041f\u043e\u0442\u043e\u043c, \u043d\u0430 \u0448\u0430\u0433\u0435 1, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043b\u043e\u0432\u043e abrakadabra. \u041f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u0441 \u044d\u0442\u0438\u043c \u0441\u043b\u043e\u0432\u043e\u043c \u0438 \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b. \u041d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0448\u0430\u0433\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e \u0434\u043b\u0438\u043d\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 brakadabra, \u0430 \u043d\u0430 \u0448\u0430\u0433\u0435 3 \u2013  \u0441\u0443\u0444\u0444\u0438\u043a\u0441 rakadabra. \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0448\u0430\u0433\u0435 4: \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 akadabra \u043c\u044b \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e, \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0435\u0435\u0441\u044f \u043d\u0430 \u0431\u0443\u043a\u0432\u0443 &#8216;\u0430&#8217;, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b &#171;\u043f\u043e\u0439\u0434\u0451\u043c&#187; \u043f\u043e \u043d\u0435\u043c\u0443 \u0438 \u0440\u0430\u0437\u0432\u0435\u0442\u0432\u0438\u043c \u0435\u0433\u043e \u0432 \u043d\u0443\u0436\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0435.<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ef4\/e51\/622\/ef4e516221f5d8844f7c90fc90d244e5.png\" width=\"601\" height=\"404\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ef4\/e51\/622\/ef4e516221f5d8844f7c90fc90d244e5.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0422\u0430\u043a \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u0442\u044c, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b, \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0434\u0435\u0440\u0435\u0432\u043e, \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0435 \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 (\u043f\u0440\u043e\u0434\u0435\u043b\u0430\u0439\u0442\u0435 \u044d\u0442\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0435 \u0443\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u0435, \u0435\u0449\u0451 \u0440\u0430\u0437 \u0441\u043c. <a href=\"https:\/\/brenden.github.io\/ukkonen-animation\/\" rel=\"noopener noreferrer nofollow\">\u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e<\/a>).<\/p>\n<p>\u041e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u043d\u0430\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435 \u0441\u0430\u043c\u044b\u0439 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439. \u041e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0448\u0430\u0433 \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u0430 \u0434\u043b\u0438\u043d\u044b <em>n<\/em> \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <em>n<\/em>, \u0441\u0430\u043c\u0438\u0445 \u0448\u0430\u0433\u043e\u0432 \u0442\u043e\u0436\u0435 <em>n<\/em>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0433\u0440\u0443\u0431\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0434\u0430\u0451\u0442 \u043e\u0446\u0435\u043d\u043a\u0443<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n^2)\" alt=\"O(n^2)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/880\/f49\/1d9\/880f491d969dde174915dba899c11e76.svg\" width=\"51\" height=\"25\"\/>. \u041d\u043e \u043c\u0435\u0441\u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e  \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u043e\u0446\u0435\u043d\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/856\/2e8\/e68\/8562e8e684b100b75c999f712bb12cc3.svg\" width=\"42\" height=\"22\"\/>. \u042d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 (\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0435\u0449\u0451 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430) \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u0438 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u043d\u0435 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f. \u041c\u0435\u0441\u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0430\u0442\u0438\u0442\u0441\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u0432\u0430 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u043a\u043e\u043d\u0446\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0442\u0435\u043a\u0441\u0442\u0430. <\/p>\n<p>\u0422\u043e, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0435\u0441\u0442\u043e<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/856\/2e8\/e68\/8562e8e684b100b75c999f712bb12cc3.svg\" width=\"42\" height=\"22\"\/>, \u0434\u0430\u0451\u0442 \u043d\u0430\u0434\u0435\u0436\u0434\u0443 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0435\u0441\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0433\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f.  \u0423\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0441\u0442\u044c, \u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ukkonen%27s_algorithm\" rel=\"noopener noreferrer nofollow\">\u0423\u043a\u043a\u043e\u043d\u0435\u043d\u0430<\/a>, \u043d\u043e \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c, \u0437\u0430\u0447\u0435\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<h2>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>ST \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b, \u043e\u043d\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u0418 \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043b\u0438 text \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 <em>x<\/em>,  \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c &#171;\u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c&#187; \u0442\u0435\u043a\u0441\u0442 <em>x<\/em>, \u0434\u0432\u0438\u0433\u0430\u044f\u0441\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u043f\u043e \u0440\u0451\u0431\u0440\u0430\u043c, \u0438 \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0443\u0434\u0430\u0451\u0442\u0441\u044f, \u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 <em>x<\/em> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u043e\u0439.<\/p>\n<p>\u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u043d\u043e \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438:<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 1: \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0435\u0441\u0442\u044c \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 <em>x<\/em> \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 2: \u041d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u043e\u0431\u0449\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445 text1 \u0438 text2.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 3: \u041d\u0430\u0439\u0442\u0438 \u0441\u0430\u043c\u0443\u044e \u0434\u043b\u0438\u043d\u043d\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text \u0431\u043e\u043b\u0435\u0435 <em>k<\/em> \u0440\u0430\u0437.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 4: \u041d\u0430\u0439\u0442\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0434\u043b\u0438\u043d\u044b <em>k<\/em>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 5: \u041d\u0430\u0439\u0434\u0438\u0442\u0435 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u0442\u043e\u043f 10 \u043f\u043e \u0447\u0430\u0441\u0442\u043e\u0442\u0435 \u0441\u043b\u043e\u0432 \u0434\u043b\u0438\u043d\u044b <em>k<\/em> \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 6: \u041d\u0430\u0439\u0442\u0438 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 <em>x<\/em>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0435\u0441\u0442\u044c  \u043e\u0434\u0438\u043d \u0441\u0438\u043c\u0432\u043e\u043b &#8216;*&#8217;, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043b\u044e\u0431\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435,  \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u043f\u0443\u0441\u0442\u043e\u0439.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 7:  \u0414\u0430\u043d\u0430 \u0431\u0430\u0437\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432. \u041d\u0430\u043f\u0438\u0448\u0438\u0442\u0435 \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043e\u0442 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0430 word, \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0432 \u0441\u043b\u043e\u0432\u0435 word \u043e\u0434\u043d\u0443 \u0438\u043b\u0438 \u0434\u0432\u0435 \u043e\u043f\u0435\u0447\u0430\u0442\u043a\u0438 \u0442\u0438\u043f\u0430 &#171;\u0437\u0430\u043c\u0435\u043d\u0430 \u043e\u0434\u043d\u043e\u0439 \u0431\u0443\u043a\u0432\u044b \u043d\u0430 \u0434\u0440\u0443\u0433\u0443&#187;, &#171;\u0443\u0434\u0430\u043b\u0435\u043d\u0430 \u043e\u0434\u043d\u0430 \u0431\u0443\u043a\u0432\u0430&#187;, &#171;\u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043e\u0434\u043d\u0430 \u043b\u0438\u0448\u043d\u044f\u044f \u0431\u0443\u043a\u0432\u0430&#187;. \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u0430 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0442\u044c 10 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0434\u043b\u044f \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0447\u0430\u0442\u043e\u043a, \u0435\u0441\u043b\u0438 \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e word \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0430 \u0431\u044b\u0441\u0442\u0440\u043e, \u043c\u043e\u0436\u043d\u043e \u0438 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 \u0431\u0430\u0437\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0438 \u043a\u0430\u043a \u0431\u044b \u043f\u0440\u043e\u0441\u0442\u044b\u0435, \u043d\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0443\u043c\u0435\u043d\u0438\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0438\u0445 <strong>\u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f<\/strong> \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u0441\u0435 \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u044b \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e ST.  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0438\u0434\u0435\u0438 \u0442\u0438\u043f\u0430<\/p>\n<ul>\n<li>\n<p>\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0443\u0437\u043b\u0430\u0445 \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u043b\u0443\u0431\u0438\u043d\u0443 \u0443\u0437\u043b\u0430 \u0432 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u0445, \u0438\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435);<\/p>\n<\/li>\n<li>\n<p>\u043f\u0435\u0440\u0435\u0434 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0432 \u043a\u043e\u043d\u0435\u0446 \u0442\u0435\u043a\u0441\u0442\u0430 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b $;<\/p>\n<\/li>\n<li>\n<p>\u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c ST \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435\u043c \u0432\u0441\u0435\u0445 \u0441\u043b\u043e\u0432 \u0432 \u043e\u0434\u0438\u043d \u0442\u0435\u043a\u0441\u0442 \u0447\u0435\u0440\u0435\u0437 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b $.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f  \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>\u0421\u0443\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 buld_tree \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u043e\u0432 &#171;a*&#187;, &#171;ab*&#187;, &#171;abr*&#187;, &#171;abra*&#187;, &#171;abrak*&#187;, &#8230; , \u0433\u0434\u0435 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0430 * \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 &#171;\u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u043b\u0438\u043f\u0448\u0438\u0435\u0441\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u044b&#187;. \u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f\u00a0<strong>\u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439<\/strong>:<\/p>\n<ul>\n<li>\n<p><em>n<\/em>\u00a0\u2013 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043f\u0435\u0440\u0435\u0434 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u043e\u0439 * , \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0447\u0435\u0441\u0442\u044c \u0438, \u043a\u0430\u043a-\u0431\u044b, \u043e\u0442\u043e\u0440\u0432\u0430\u0442\u044c \u043e\u0442 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0438 (\u0441\u043e\u0440\u0440\u0438, \u0440\u0430\u043d\u044c\u0448\u0435 n \u0431\u044b\u043b\u043e \u0440\u0430\u0432\u043d\u043e \u0434\u043b\u0438\u043d\u0435 \u0442\u0435\u043a\u0441\u0442\u0430, \u0442\u0435\u043f\u0435\u0440\u044c \u044d\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0439 \u0431\u0443\u043a\u0432\u044b) \u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u043e;<\/p>\n<\/li>\n<li>\n<p>node \u2013 \u0443\u0437\u0435\u043b \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u044b \u0448\u0430\u0433\u0430\u0435\u043c \u0432 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442;<\/p>\n<\/li>\n<li>\n<p>edge \u2013 \u0440\u0435\u0431\u0440\u043e, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043c\u044b \u0448\u0430\u0433\u0430\u0435\u043c; \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u043e\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 (first, last) \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0435 text[first: last];<\/p>\n<\/li>\n<li>\n<p>i \u2013 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432\u043d\u0443\u0442\u0440\u0438 [first, last], \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u0434\u0430\u0451\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043d\u0430 \u0440\u0435\u0431\u0440\u0435, \u0433\u0434\u0435 \u0438\u043c\u0435\u043d\u043d\u043e \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f.<\/p>\n<\/li>\n<\/ul>\n<p>\u0415\u0441\u0442\u044c \u0435\u0449\u0451 \u0441\u043a\u0440\u044b\u0442\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 j, \u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e \u0442\u0435\u043a\u0441\u0442 text[j: first-1] \u043a\u0430\u043a \u0440\u0430\u0437 \u043f\u0440\u0438\u0432\u0451\u043b \u0431\u044b \u043d\u0430\u0441 \u0438\u0437 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 node. \u0411\u0443\u0434\u0435\u043c \u044d\u0442\u043e\u0442 \u0444\u0430\u043a\u0442 \u0443\u0441\u043b\u043e\u0432\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430<br \/>node = Node(text[j:first-1]).<\/p>\n<p>\u0412 \u043c\u0435\u0442\u043e\u0434\u0435 build_tree(node, n) \u0432\u043d\u0443\u0442\u0440\u0438 \u0446\u0438\u043a\u043b\u0430 while \u043c\u044b <em>\u043a\u0430\u043a \u0431\u044b<\/em> \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u043a\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 text[j:end] \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438.\u00a0<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043c\u044b \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b\u0438 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0442\u0435\u043a\u0441\u0442 text[j:n] \u0438 \u0445\u043e\u0442\u0438\u043c \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0434\u0430\u043b\u044c\u0448\u0435, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e, \u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b text[n+1] \u043d\u0430 \u0440\u0435\u0431\u0440\u0435 edge. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u043d\u0430 1 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 n \u0438 i \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0432\u0435\u0440\u043d\u043e \u043b\u0438, \u0447\u0442\u043e text[i] == text[n], \u0438 \u0435\u0441\u043b\u0438 \u0432\u0435\u0440\u043d\u043e, \u0442\u043e \u0434\u0432\u0438\u0433\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u0440\u0435\u0431\u0440\u0443 \u0434\u0430\u043b\u044c\u0448\u0435. \u0412 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043c\u043e\u043c\u0435\u043d\u0442 \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u0435 \u043f\u043e \u0440\u0435\u0431\u0440\u0443 \u043e\u0431\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u043e\u0432\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043d\u0435 \u0442\u043e\u0442: text[i] != text[n]. \u0418 \u0442\u043e\u0433\u0434\u0430 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b <strong>\u0432\u0440\u0435\u0437\u0430\u0442\u044c \u0432 \u0440\u0435\u0431\u0440\u043e<\/strong> (\u0432\u00a0<strong>\u0430\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443<\/strong>) <strong>\u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b<\/strong> \u0438 \u043e\u0442\u0432\u0435\u0442\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u043d\u0435\u0433\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435\u043c text[n: end].<\/p>\n<p>\u0418 \u0432\u043e\u0442 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442: \u043a\u043e\u0433\u0434\u0430 \u043c\u044b, \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b new_node=Node(text[j:n]), \u043c\u044b\u00a0<strong>\u0434\u0435\u043b\u0430\u0435\u043c \u0435\u0449\u0451 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432<\/strong>\u00a0\u2013 \u043e\u0442\u0432\u043b\u0435\u043a\u0430\u0435\u043c\u0441\u044f \u043d\u0430 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0443 &#171;\u043f\u0440\u043e\u0439\u0442\u0438 \u043f\u0443\u0442\u044c text[first:n] \u0438\u0437 \u0443\u0437\u043b\u0430 Node(text[j+1:first-1]) \u0438 \u0442\u0430\u043c \u0442\u043e\u0436\u0435, \u0435\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e, \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043d\u0435\u0433\u043e&#187;.\u00a0<\/p>\n<p>\u0415\u0449\u0451 \u0440\u0430\u0437: \u0434\u0432\u0438\u0433\u0430\u044f\u0441\u044c \u0442\u0435\u043a\u0441\u0442\u043e\u043c text[n-k: n] \u0438\u0437 node=Node(text[j:first-1]) \u043f\u043e \u0440\u0435\u0431\u0440\u0443 text[first:last] \u0438 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0432\u0448\u0438\u0441\u044c \u0441 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c\u044e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b new_node=Node(text[j:n]), \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043c\u043e\u0436\u0435\u0442 \u0436\u0434\u0430\u0442\u044c \u043d\u0430\u0441 \u043d\u0430 \u043f\u0443\u0442\u0438 \u0438\u0437 suff_node=Node(text[j+1:first-1]), \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u043e\u0439\u0434\u0451\u043c \u0438\u0437 \u043d\u0435\u0433\u043e \u0442\u0435\u043c \u0436\u0435 \u0442\u0435\u043a\u0441\u0442\u043e\u043c text[n-k: n]. \u0418 \u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438. \u041f\u0440\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u044d\u0442\u043e\u0439 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438, \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438 \u0443\u0436\u0435 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 Node(text[j+2: first-1]) \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>\u0412\u0430\u0436\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u2013 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0438 \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0443\u0437\u043b\u0430\u0445 Node(text[j:x]) \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u0443\u0437\u0435\u043b Node(text[j+1:x]). \u041d\u0430\u0437\u043e\u0432\u0451\u043c \u0442\u0430\u043a\u0438\u0435 \u0441\u0441\u044b\u043b\u043a\u0438\u00a0<strong>\u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u044b\u043c\u0438 \u0441\u0441\u044b\u043b\u043a\u0430\u043c\u0438<\/strong>. \u042d\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u0438\u0442 \u043d\u0430\u043c \u043d\u0435 \u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043d\u0430 \u043f\u043e\u0438\u0441\u043a \u0443\u0437\u043b\u0430 Node(text[j+1:x]) \u0434\u043b\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u0433\u043e \u0432\u044b\u0437\u043e\u0432\u0430. \u0414\u0435\u043b\u0430\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432, \u043f\u043e\u043b\u0435\u0437\u043d\u043e \u0442\u0430\u043a\u0436\u0435 \u043f\u0435\u0440\u0435\u0434\u0430\u0442\u044c <em>\u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0440\u043e\u0440\u0430\u0431\u043e\u0442\u0430\u043d\u043d\u044b\u0445 \u043f\u0435\u0440\u0432\u044b\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432<\/em> \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text[n-k:n], \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0443\u0436\u0435 \u0434\u043e\u043b\u0436\u043d\u044b <em>\u0443\u043c\u0435\u0442\u044c \u0447\u0438\u0442\u0430\u0442\u044c\u0441\u044f<\/em>\u00a0\u0438\u0437 \u0443\u0437\u043b\u0430 Node(text[j+1:x]) (\u0442\u043e \u0435\u0441\u0442\u044c \u0434\u043b\u044f \u043d\u0438\u0445 \u0434\u043e\u043b\u0436\u0435\u043d \u0431\u044b\u0442\u044c \u043f\u0443\u0442\u044c \u0438\u0437 \u0432\u0435\u0440\u0448\u0438\u043d\u044b Node(text[j+1:x])). \u042d\u0442\u043e\u0442 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043a\u043e\u0434\u0435 skip.<\/p>\n<p>\u0414\u0430\u043b\u0435\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043c\u0435\u0434\u0438\u0442\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u043d\u0430 \u043a\u043e\u0434, \u043a\u043e\u0442\u043e\u0440\u044b\u0439, \u0432 \u043e\u0442\u043b\u0438\u0447\u0438\u0435 \u043e\u0442 \u0440\u0443\u0441\u0441\u043a\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430, \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043e\u0434\u043d\u043e\u0437\u043d\u0430\u0447\u043d\u044b\u0439 \u0438 \u043f\u043e\u043b\u043d\u044b\u0439.<\/p>\n<pre><code class=\"python\">from collections import defaultdict from typing import Optional   class Node:     text = \"\"  # for debug purpose      def __init__(self, edges=None, suff_link=None, parent=None):         self.edges = edges if edges is not None else defaultdict(type(None))         self.suff_link: Optional[Node] = suff_link         self.parent: Optional[Node] = parent      def __str__(self):         if self.parent:             idxs = [e.idxs for e in self.parent.edges.values() if e.target_node == self][0]             return f\"{self.parent}{self.text[idxs[0]: idxs[1]]}_\"         else:             return \"_\"   class Edge:     def __init__(self, idxs=None, target_node=None):         self.idxs = idxs         self.target_node: Optional[Node] = target_node   class SuffixTree:     # node =  &lt; suffix_link, parent, edges >     # edges = { first_char => edge }     # edge =  &lt; idxs, target_node >     # idxs = (first, last) # corresponds to label = text[first: last]     def __init__(self, text):         self.text = text         self.joker_edge = Edge(idxs=(0, 1))         self.joker = Node(edges=defaultdict(lambda: self.joker_edge))         self.root = Node(suff_link=self.joker)         self.joker_edge.target_node = self.root         self.infty = len(self.text)         self._build_tree(self.root, 0, self.infty)      def __str__(self):         return f\"SuffixTree(text='{self.text}')\"      def pp(self, node=None, indent=0):         node = node or self.root         space = \"    \" * indent         print(space + f\"ID    : {node}\")         print(space + f\"link  : {node.suff_link}\")         print(space + f\"edges : \")          for c, edge in node.edges.items():             print(space + f\"  -{c} {edge.idxs}={self.text[edge.idxs[0]: edge.idxs[1]]}:\")             self.pp(edge.target_node, indent + 1)      def _build_tree(self, node: Node, n: int, infty: int, skip: int = 0):         while n &lt; infty:             c = self.text[n]             edge = node.edges[c]             if edge is not None:                 first, last = edge.idxs                 i, n0 = first, n                 if skip > 0:                     can_skip = min(skip, last - first)                     i += can_skip                     n += can_skip                     skip -= can_skip                  while (                     i &lt; last and n &lt; infty and                     (self.text[i] == self.text[n] or edge is self.joker_edge)                 ):                     i += 1                     n += 1                  if i == last:  # go to the next node                     node = edge.target_node                 else:  # splitting edge                     middle_node = Node(parent=node)                     middle_node.edges[self.text[i]] = edge                     node.edges[c] = Edge(idxs=(first, i), target_node=middle_node)                     edge.idxs = (i, edge.idxs[1])                     edge.target_node.parent = middle_node                     middle_node.suff_link = self._build_tree(node.suff_link, n0, n, i - first)                     node = middle_node             else:  # no way to go; creating new leaf                 new_leaf = Node(parent=node)                 node.edges[c] = Edge(idxs=(n, self.infty), target_node=new_leaf)                 node = node.suff_link         return node   text = \"abrakadabra\" Node.text = text tree = SuffixTree(text)  tree.pp()<\/code><\/pre>\n<details class=\"spoiler\">\n<summary>\u0412\u044b\u0445\u043b\u043e\u043f \u044d\u0442\u043e\u0433\u043e \u043a\u043e\u0434\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u0442\u0430\u043a \u2193<\/summary>\n<div class=\"spoiler__content\">\n<pre><code>ID    : _ link  : _ edges :    -a (0, 1)=a:     ID    : _a_     link  : _     edges :        -b (1, 4)=bra:         ID    : _a_bra_         link  : _bra_         edges :            -k (4, 11)=kadabra:             ID    : _a_bra_kadabra_             link  : None             edges :        -k (4, 11)=kadabra:         ID    : _a_kadabra_         link  : None         edges :        -d (6, 11)=dabra:         ID    : _a_dabra_         link  : None         edges :    -b (1, 4)=bra:     ID    : _bra_     link  : _ra_     edges :        -k (4, 11)=kadabra:         ID    : _bra_kadabra_         link  : None         edges :    -r (2, 4)=ra:     ID    : _ra_     link  : _a_     edges :        -k (4, 11)=kadabra:         ID    : _ra_kadabra_         link  : None         edges :    -k (4, 11)=kadabra:     ID    : _kadabra_     link  : None     edges :    -d (6, 11)=dabra:     ID    : _dabra_     link  : None     edges : <\/code><\/pre>\n<\/p>\n<\/div>\n<\/details>\n<p>\u041d\u0435 \u0432\u0441\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u044b\u0435 \u0441\u0441\u044b\u043b\u043a\u0438 \u0441\u043e\u0437\u0434\u0430\u044e\u0442\u0441\u044f, \u043e\u043d\u0438 \u0441\u043e\u0437\u0434\u0430\u044e\u0442\u0441\u044f \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438. \u041d\u0430 \u043a\u0430\u0440\u0442\u0438\u043d\u043a\u0435 \u043d\u0438\u0436\u0435 \u043f\u0443\u043d\u043a\u0442\u0438\u0440\u043e\u043c \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u044b \u0434\u0432\u0435 \u0442\u0430\u043a\u0438\u0435 \u0441\u0441\u044b\u043b\u043a\u0438:<\/p>\n<figure class=\"full-width\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/a3d\/025\/189\/a3d025189ed829861a8a1ae811473558.png\" width=\"1168\" height=\"980\" data-src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a3d\/025\/189\/a3d025189ed829861a8a1ae811473558.png\"\/><figcaption><\/figcaption><\/figure>\n<p>\u0423 \u043c\u0435\u043d\u044f \u0431\u0443\u0434\u0435\u0442 \u043e\u0447\u0435\u043d\u044c \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u043e\u0431\u044a\u044f\u0441\u043d\u0435\u043d\u0438\u0435, \u043f\u043e\u0447\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f. \u0412\u00a0<a href=\"https:\/\/brenden.github.io\/ukkonen-animation\/\" rel=\"noopener noreferrer nofollow\">\u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430<\/a>\u00a0\u0431\u0443\u043a\u0432\u044b \u0438\u043c\u0435\u044e\u0442 \u0442\u0440\u0438 \u0446\u0432\u0435\u0442\u0430:<\/p>\n<ul>\n<li>\n<p>\u0431\u0435\u043b\u044b\u0439 \u2013 \u043d\u0435\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0431\u0443\u043a\u0432\u044b, \u0442\u043e \u0435\u0441\u0442\u044c \u0431\u0443\u043a\u0432\u044b, <em>\u0441\u043b\u0438\u043f\u0448\u0438\u0435\u0441\u044f<\/em> \u0432 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0443; \u0441\u0430\u043c\u043e\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u0431\u0435\u043b\u043e\u0439 \u0431\u0443\u043a\u0432\u043e\u0439 \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043a\u0430\u043a \u0440\u0430\u0437 \u0437\u0430\u043d\u0438\u043c\u0430\u0442\u044c\u0441\u044f \u0432 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442;<\/p>\n<\/li>\n<li>\n<p>\u0437\u0435\u043b\u0435\u043d\u044b\u0439 \u2013 \u0431\u0443\u043a\u0432\u044b, \u043a\u043e\u0442\u043e\u0440\u044b\u043c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0435\u0449\u0451 \u043f\u0440\u0435\u0434\u0441\u0442\u043e\u0438\u0442 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c;<\/p>\n<\/li>\n<li>\n<p>\u0433\u043e\u043b\u0443\u0431\u043e\u0439 \u2013 \u0431\u0443\u043a\u0432\u044b, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b \u0443\u0436\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u044b (\u043f\u0443\u0441\u0442\u044c \u0441\u043e \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u043e\u0439 \u043d\u0430 \u043a\u043e\u043d\u0446\u0435).<\/p>\n<\/li>\n<\/ul>\n<p>\u041d\u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u043d\u0430\u0436\u0430\u0442\u0438\u0435 \u043a\u043d\u043e\u043f\u043a\u0438 Next \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0442\u0440\u0430\u0442\u0438\u0442 \u0432\u0440\u0435\u043c\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(1)\" alt=\"O(1)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0cb\/9fd\/1b3\/0cb9fd1b333936cb80145213f704162e.svg\" width=\"40\" height=\"22\"\/>(\u0437\u0430\u0434\u0430\u0447\u0430 \u0434\u043b\u044f \u0441\u0430\u043c\u043e\u0441\u0442\u043e\u044f\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0448\u0435\u043d\u0438\u044f). \u0422\u0430\u043a\u0438\u0445 \u043d\u0430\u0436\u0430\u0442\u0438\u0439 \u0431\u0443\u0434\u0435\u0442 \u043d\u0435 \u0431\u043e\u043b\u0435\u0435, \u0447\u0435\u043c 2 * len(text), \u0442\u0430\u043a \u043a\u0430\u043a \u043a\u0430\u0436\u0434\u043e\u0435 \u043d\u0430\u0436\u0430\u0442\u0438\u0435 \u2013 \u044d\u0442\u043e \u043b\u0438\u0431\u043e \u0437\u0430\u043a\u0440\u0430\u0448\u0438\u0432\u0430\u043d\u0438\u0435 \u0431\u0443\u043a\u0432\u044b \u0432 \u0437\u0435\u043b\u0451\u043d\u044b\u0439 \u0438\u043b\u0438 \u0433\u043e\u043b\u0443\u0431\u043e\u0439 \u0446\u0432\u0435\u0442 \u0438\u043b\u0438 \u043f\u0435\u0440\u0435\u043a\u0440\u0430\u0448\u0438\u0432\u0430\u043d\u0438\u0435 \u0437\u0435\u043b\u0451\u043d\u043e\u0439 \u0431\u0443\u043a\u0432\u044b \u0432 \u0433\u043e\u043b\u0443\u0431\u043e\u0439.<\/p>\n<p>\u041c\u043e\u044f \u0441\u0442\u0430\u0442\u044c\u044f \u043f\u0440\u043e \u043a\u0440\u0430\u0442\u043a\u043e\u0441\u0442\u044c. \ud83d\ude42 \u0415\u0441\u043b\u0438 \u0432\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0434\u0440\u043e\u0431\u043d\u0435\u0435 \u0438 \u0442\u043e\u0447\u043d\u0435\u0435, \u0442\u043e \u0447\u0438\u0442\u0430\u0439\u0442\u0435\u00a0<a href=\"https:\/\/stackoverflow.com\/questions\/9452701\/ukkonens-suffix-tree-algorithm-in-plain-english\/9513423#9513423\" rel=\"noopener noreferrer nofollow\">\u043e\u0442\u0432\u0435\u0442 \u043d\u0430 stackoverflow.<\/a><\/p>\n<h2>\u041f\u0440\u043e  Suffix Array<\/h2>\n<p>\u0412\u044b\u0448\u0435 \u043c\u044b \u043d\u0430\u0447\u0430\u043b\u0438 \u0440\u0430\u0437\u0433\u043e\u0432\u043e\u0440 \u0441 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432:<\/p>\n<p><code>abrakadabra\"<br \/>\"abra\"<br \/>\"adabra\"<br \/>\"akadabra\"<br \/>\"a\" <br \/>\"brakadabra\" <br \/>\"bra\" <br \/>\"dabra\" <br \/>\"kadabra\" <br \/>\"rakadabra\" <br \/>\"ra\"<\/code><\/p>\n<p>\u041e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 (\u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u0435\u0433\u043e \u043d\u0430\u0447\u0430\u043b\u0430), \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f  \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c  (<a href=\"https:\/\/e-maxx.ru\/algo\/suffix_array\" rel=\"noopener noreferrer nofollow\">Suffix Array<\/a>). \u041a\u0430\u043a \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c \u0442\u0430\u043a\u043e\u0439 \u043c\u0430\u0441\u0441\u0438\u0432? \u041f\u043e\u043f\u044b\u0442\u043a\u0430 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443 \u0432 \u043b\u043e\u0431, \u0432\u044b\u0437\u0432\u0430\u0432 \u043c\u0435\u0442\u043e\u0434 sort, \u0434\u0430\u0441\u0442 \u043a\u0432\u0430\u0434\u0440\u0430\u0442\u0438\u0447\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0430 \u0442\u043e\u0447\u043d\u0435\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n^2 \\log(n))\" alt=\"O(n^2 \\log(n))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/59e\/f72\/721\/59ef72721bdc14643e285e45e60c6e65.svg\" width=\"106\" height=\"25\"\/>.  \u0414\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043e\u0446\u0435\u043d\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n \\log (n))\" alt=\"O(n \\log (n))\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b4f\/6e7\/80b\/b4f6e780be289527800477c817b40635.svg\" width=\"97\" height=\"22\"\/>, \u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u0430\u0451\u0442 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n)\" alt=\"O(n)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c24\/58f\/c09\/c2458fc09fa12a8ecc0685c34f99f39b.svg\" width=\"42\" height=\"22\"\/>, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u043e\u0433\u0434\u0430 \u0442\u0435\u043a\u0441\u0442 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430.<\/p>\n<p>\u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0435\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u2013 \u0438 \u044d\u0442\u043e \u0445\u043e\u0440\u043e\u0448\u0430\u044f \u0442\u0435\u043c\u0430 \u0434\u043b\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0438. \u041e\u0434\u043d\u0430 \u0438\u0437 \u043f\u0440\u043e\u0441\u0442\u044b\u0445 \u0438\u0434\u0435\u0439 (\u043d\u043e \u043d\u0435 \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0449\u0438\u0445) \u2013 \u043e\u0431\u044b\u0447\u043d\u044b\u0439 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c QuickSort, \u0442\u043e\u043b\u044c\u043a\u043e \u0432 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u043e\u043c \u0432\u044b\u0437\u043e\u0432\u0435 \u043d\u0443\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0434\u0430\u0432\u0430\u0442\u044c \u0434\u043b\u0438\u043d\u0443 \u043e\u0431\u0449\u0435\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430 \u0443 \u0432\u0441\u0435\u0445 \u0441\u0442\u0440\u043e\u043a \u0432 \u0441\u043e\u0440\u0442\u0438\u0440\u0443\u0435\u043c\u043e\u043c \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432\u0435. Suffix Array \u043f\u0440\u043e\u0449\u0435 \u0434\u043b\u044f \u043f\u043e\u043d\u0438\u043c\u0430\u043d\u0438\u044f, \u0432 \u043d\u0451\u043c \u043c\u043e\u0436\u043d\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u0438\u0432\u044b\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u043c\u0435\u0442\u043e\u0434\u043e\u043c \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043f\u043e\u043b\u0430\u043c (\u043d\u043e \u043d\u0443\u0436\u043d\u0430 mlr-\u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f), \u0438 \u0435\u0449\u0451 \u0438\u0437 Suffix Array \u043c\u043e\u0436\u043d\u043e \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c ST, \u0438 \u044d\u0442\u043e \u0434\u0430\u0451\u0442 \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f.<\/p>\n<\/p>\n<\/div>\n<\/div>\n<\/div>\n<div class=\"v-portal\" style=\"display:none;\"><\/div>\n<\/div>\n<p> <!----> <!----><br \/> \u0441\u0441\u044b\u043b\u043a\u0430 \u043d\u0430 \u043e\u0440\u0438\u0433\u0438\u043d\u0430\u043b \u0441\u0442\u0430\u0442\u044c\u0438 <a href=\"https:\/\/habr.com\/ru\/post\/681940\/\"> https:\/\/habr.com\/ru\/post\/681940\/<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<div><\/div>\n<div id=\"post-content-body\">\n<div>\n<div class=\"article-formatted-body article-formatted-body article-formatted-body_version-2\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\">\n<p>\u0421\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e  (Suffix Tree, ST)  \u2013 \u044d\u0442\u043e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0430 \u0434\u0430\u043d\u043d\u044b\u0445,  \u043a\u043e\u0442\u043e\u0440\u0430\u044f  \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 &#171;\u043f\u0440\u043e\u0438\u043d\u0434\u0435\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u0442\u044c&#187; \u0441\u0442\u0440\u043e\u043a\u0443 \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0442 \u0435\u0451 \u0434\u043b\u0438\u043d\u044b, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0442\u043e\u043c \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 (\u0437\u0430 \u0432\u0440\u0435\u043c\u044f \u041e(\u0434\u043b\u0438\u043d\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438)).<\/p>\n<p>\u0422\u0435\u043c\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u0438 \u0435\u0433\u043e \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f  \u0445\u043e\u0440\u043e\u0448\u043e \u0440\u0430\u0441\u043a\u0440\u044b\u0442\u0430 \u0432 \u0438\u043d\u0442\u0435\u0440\u043d\u0435\u0442 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree\" rel=\"noopener noreferrer nofollow\">\u0432\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a>, <a href=\"https:\/\/habr.com\/ru\/post\/258121\/\" rel=\"noopener noreferrer nofollow\">\u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0412\u0435\u0439\u043d\u0435\u0440\u0430, \u044f\u0437\u044b\u043a \u0421\u0438<\/a>, \u0438 <a href=\"https:\/\/habr.com\/ru\/post\/533774\/\" rel=\"noopener noreferrer nofollow\">\u0441\u0442\u0430\u0442\u044c\u044f \u043d\u0430 \u0445\u0430\u0431\u0440 \u043f\u0440\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c  \u0423\u043a\u043a\u043e\u043d\u0435\u043d\u0430<\/a>).<br \/>\u041d\u043e \u0432\u0441\u0435\u0433\u0434\u0430 \u0435\u0441\u0442\u044c \u0441\u043e\u0431\u043b\u0430\u0437\u043d \u043f\u043e\u0443\u0447\u0430\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0432 \u0441\u043e\u0440\u0435\u0432\u043d\u043e\u0432\u0430\u043d\u0438\u0438 &#171;\u043d\u0430\u043f\u0438\u0441\u0430\u0442\u044c \u043f\u0440\u043e\u0449\u0435 \u0438 \u044f\u0441\u043d\u0435\u0435&#187;, \u0445\u043e\u0442\u044f \u0448\u0430\u043d\u0441\u043e\u0432 \u043c\u0430\u043b\u043e. \u0422\u0435\u043c \u043d\u0435 \u043c\u0435\u043d\u0435\u0435, \u0440\u0438\u0441\u043a\u043d\u0443.<\/p>\n<p>\u0421\u043e\u0431\u043b\u0430\u0437\u043d \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u0432 \u0441\u0432\u044f\u0437\u0438 \u0441\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c\u0438 \u043c\u043e\u043c\u0435\u043d\u0442\u0430\u043c\u0438:<\/p>\n<ul>\n<li>\n<p>\u0412 \u043d\u0430\u0441\u0442\u0443\u043f\u0438\u0432\u0448\u0435\u043c \u043c\u0438\u0440\u0435 \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 \u0441\u043e\u0432\u0435\u0440\u0435\u0448\u0435\u043d\u043d\u043e \u043d\u0435\u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u043a\u0430\u043a \u0431\u044b \u043c\u044b \u0436\u0438\u043b\u0438 \u0431\u0435\u0437 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0445\u043e\u0436\u0438\u0445 \u043a\u0443\u0441\u043e\u0447\u043a\u043e\u0432 \u0432 \u0433\u0438\u0433\u0430\u0431\u0430\u0439\u0442\u0430\u0445 \u0434\u0430\u043d\u043d\u044b\u0445 (\u043f\u043e\u0438\u0441\u043a \u0441\u0442\u0440\u043e\u043a \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445, \u0440\u0430\u0441\u0448\u0438\u0444\u0440\u043e\u0432\u043a\u0430 \u0414\u041d\u041a,  \u0430\u043d\u0442\u0438\u043f\u043b\u0430\u0433\u0438\u0430\u0442, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0441\u0436\u0430\u0442\u0438\u044f \u0437\u0430 \u0441\u0447\u0435\u0442 \u0432\u044b\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u0439 \u0438 \u0434\u0440.). Suffix Tree \u0438 Suffix Array \u2013 \u0433\u043b\u0430\u0432\u043d\u044b\u0435  \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445, \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0449\u0438\u0435 \u0440\u0435\u0448\u0430\u0442\u044c \u0432\u0441\u0435 \u044d\u0442\u0438 \u0437\u0430\u0434\u0430\u0447\u0438.<\/p>\n<\/li>\n<li>\n<p>ST \u043f\u043e \u043f\u0440\u0430\u0432\u0443 \u0441\u0447\u0438\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0439 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u043e\u0439 \u0434\u0430\u043d\u043d\u044b\u0445. \u0415\u0441\u043b\u0438 \u0432 \u0438\u043d\u0441\u0442\u0438\u0442\u0443\u0442\u0435 \u043d\u0430 \u044d\u043a\u0437\u0430\u043c\u0435\u043d\u0435 \u0432\u0430\u0441 \u0441\u043f\u0440\u0430\u0448\u0438\u0432\u0430\u044e\u0442 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST, \u0435\u0441\u0442\u044c \u0441\u0435\u0440\u044c\u0451\u0437\u043d\u044b\u0435 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0432\u0430\u0441 \u0432\u0430\u043b\u044f\u0442.<\/p>\n<\/li>\n<li>\n<p>\u041d\u0435\u0441\u043c\u043e\u0442\u0440\u044f \u043d\u0430 \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u0443\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0432 35 \u0441\u0442\u0440\u043e\u043a \u043d\u0430 python (\u0441\u043c. \u043d\u0438\u0436\u0435 \u043c\u0435\u0442\u043e\u0434 _build_tree). \u0418\u0445 \u0431\u0443\u043a\u0432\u0430\u043b\u044c\u043d\u043e \u043c\u043e\u0436\u043d\u043e \u0432\u044b\u0443\u0447\u0438\u0442\u044c \u0438 \u0432\u043e\u0441\u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u044c \u043f\u043e \u043f\u0430\u043c\u044f\u0442\u0438 \u043a\u0430\u043a \u043d\u0435\u043a\u043e\u0435 \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0434\u0435\u043d\u0438\u0435 \u0438\u0441\u043a\u0443\u0441\u0441\u0442\u0432\u0430, \u043a\u0430\u043a \u0432\u043e\u043f\u043b\u043e\u0449\u0435\u043d\u043d\u044b\u0439 \u0432 \u043d\u0430\u0431\u043e\u0440 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0442\u0440\u0443\u0434 \u0447\u0435\u043b\u043e\u0432\u0435\u0447\u0435\u0441\u043a\u043e\u0439 \u043c\u044b\u0441\u043b\u0438, \u043f\u0440\u0438\u0447\u0451\u043c \u043d\u0435 \u043e\u0434\u043d\u043e\u0433\u043e \u0447\u0435\u043b\u043e\u0432\u0435\u043a\u0430, \u0438 \u043f\u0435\u0440\u0432\u044b\u0435 \u0438\u0437 \u043d\u0438\u0445 \u0442\u043e\u0447\u043d\u043e \u0433\u0435\u043d\u0438\u0438. \ud83d\ude42 \u0415\u0441\u0442\u044c \u0441\u043e\u0431\u043b\u0430\u0437\u043d, \u0432\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u044f\u0441\u044c \u0432 \u043a\u043e\u0434, \u043f\u0440\u0438\u043a\u043e\u0441\u043d\u0443\u0442\u044c\u0441\u044f \u043a \u0432\u0435\u043b\u0438\u043a\u043e\u043c\u0443 \u0438 \u0447\u0435\u043c\u0443-\u0442\u043e \u043d\u0430\u0443\u0447\u0438\u0442\u044c\u0441\u044f.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0435\u0440\u0432\u044b\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u043e\u0442\u043d\u043e\u0441\u0438\u0442\u0441\u044f \u043a 1973  \u0433\u043e\u0434\u0443, \u043d\u043e \u043d\u043e\u0432\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0443\u043b\u0443\u0447\u0448\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u043b\u0438 \u0432\u0441\u0451 \u044d\u0442\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u044f\u0432\u043b\u044f\u0442\u044c\u0441\u044f:<\/p>\n<ul>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree#CITEREFWeiner1973\" rel=\"noopener noreferrer nofollow\">Weiner<\/a>, 1973 \u2013 \u043f\u0435\u0440\u0432\u044b\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f ST \u043e\u0442 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u0435\u0440\u0432\u043e\u043c\u0443.<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Ukkonen%27s_algorithm\" rel=\"noopener noreferrer nofollow\">Ukkonen&#8217;s algorithm<\/a>, 1995 \u2013 \u043f\u0435\u0440\u0432\u044b\u0439 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c\u0443,  \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u043e\u043d\u043b\u0430\u0439\u043d (\u043a\u043e\u0433\u0434\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0431\u0435\u0440\u0443\u0442\u0441\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0438\u0437 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043f\u043e\u0442\u043e\u043a\u0430).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Suffix_tree#CITEREFFarach1997\" rel=\"noopener noreferrer nofollow\">Farach<\/a>, 1997 \u2013 Optimal suffix tree construction with large alphabets \u2013 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u043e\u0432 \u043b\u044e\u0431\u043e\u0439 \u0434\u043b\u0438\u043d\u044b (\u0432 \u043e\u0446\u0435\u043d\u043a\u0435 \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0434\u043b\u0438\u043d\u0430 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430).<\/p>\n<\/li>\n<li>\n<p><a href=\"https:\/\/core.ac.uk\/download\/pdf\/82790401.pdf\" rel=\"noopener noreferrer nofollow\">Dany Breslauer, Giuseppe F. Italiano<\/a>,  2011 \u2013 Near real-time suffix tree construction \u2013 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u043e\u043d\u043b\u0430\u0439\u043d \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0432 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c Ukkonen&#8217;s algorithm, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e, \u0432\u043c\u0435\u0441\u0442\u043e , \u0433\u0434\u0435  \u2013 \u0434\u043b\u0438\u043d\u0430  \u0442\u0435\u043a\u0441\u0442\u0430, \u043d\u043e \u0437\u0430\u0442\u043e \u0438 \u0441\u0440\u0435\u0434\u043d\u0435\u0435, \u0438 \u0445\u0443\u0434\u0448\u0435\u0435 \u0445\u0443\u0434\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0440\u0430\u0432\u043d\u043e, \u0430 \u0443 Ukkonen&#8217;s algorithm \u043d\u0430 \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0443 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043c\u043e\u0436\u0435\u0442 \u0443\u0439\u0442\u0438 \u0432\u0440\u0435\u043c\u044f .<\/p>\n<\/li>\n<\/ul>\n<h2>\u0427\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e<\/h2>\n<p>\u0412\u043e\u0437\u044c\u043c\u0451\u043c \u0442\u0435\u043a\u0441\u0442 &#171;abrakadabra&#187;.<\/p>\n<p>\u041c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u044d\u0442\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430 \u2013 \u044d\u0442\u043e \u0441\u0442\u0440\u043e\u043a\u0438<\/p>\n<p><code>abrakadabra<br \/>brakadabra<br \/>rakadabra<br \/>akadabra<br \/>kadabra<br \/>adabra<br \/>dabra<br \/>abra<br \/>bra<br \/>ra<br \/>a<\/code><\/p>\n<p>\u0418\u0445 \u043c\u043e\u0436\u043d\u043e \u043f\u0435\u0440\u0435\u0443\u043f\u043e\u0440\u044f\u0434\u043e\u0447\u0438\u0442\u044c \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0438\u0437\u043e\u0448\u043b\u043e <strong>\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e &#171;\u0441\u043a\u043b\u0435\u0435\u043a&#187; \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u0441\u0442\u0440\u043e\u043a \u043f\u043e \u043f\u0435\u0440\u0432\u044b\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c<\/strong>:<\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0442\u0430\u043a<\/p>\n<p><code>abrakadabra<br \/>abra<br \/>adabra<br \/>akadabra<br \/>a<br \/>brakadabra<br \/>bra<br \/>rakadabra<br \/>ra<br \/>kadabra<br \/>dabra<\/code><\/p>\n<details class=\"spoiler\">\n<summary>\u0414\u043b\u044f &#171;\u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u043a\u043b\u0435\u0439\u043a\u0438&#187; \u043f\u043e\u0434\u043e\u0439\u0434\u0451\u0442 \u0438 \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u043a\u0430 \u043f\u043e \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0443 <\/summary>\n<div class=\"spoiler__content\">\n<p>\u041a\u0441\u0442\u0430\u0442\u0438, \u044d\u0442\u043e\u0442 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0438 \u0435\u0441\u0442\u044c Suffix Array):<code><br \/>a<br \/>adabra<br \/>abra<br \/>abrakadabra<br \/>akadabra<br \/>bra<br \/>brakadabra<br \/>dabra<br \/>kadabra<br \/>ra<br \/>rakadabra<\/code><\/p>\n<\/div>\n<\/details>\n<p>\u0412 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442\u0435 <strong>\u0441\u043a\u043b\u0435\u0439\u043a\u0438 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0445 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0445 \u043f\u043e \u0432\u0435\u0440\u0442\u0438\u043a\u0430\u043b\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432<\/strong> \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e:<\/p>\n<figure class=\"\"><figcaption><\/figcaption><\/figure>\n<p>\u042d\u0442\u043e \u0438 \u0435\u0441\u0442\u044c \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e: \u0434\u0435\u0440\u0435\u0432\u043e, \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u0435\u0441\u0442\u044c \u0432\u044b\u0434\u0435\u043b\u0435\u043d\u043d\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430 \u2013 \u043a\u043e\u0440\u0435\u043d\u044c (\u0441\u0430\u043c\u0430\u044f \u043b\u0435\u0432\u0430\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430), \u0438 \u0443 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043d\u0430 \u0440\u0451\u0431\u0440\u0430\u0445 \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0442\u0435\u043a\u0441\u0442\u0430. \u041b\u044e\u0431\u043e\u0439 \u043f\u0443\u0442\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u043e \u043a\u0430\u043a\u043e\u0439-\u043b\u0438\u0431\u043e \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u0442\u0440\u043e\u043a\u0435, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435\u043c \u0441\u0442\u0440\u043e\u043a, \u043d\u0430\u043f\u0438\u0441\u0430\u043d\u044b\u0445 \u043d\u0430 \u0440\u0451\u0431\u0440\u0430\u0445.\u00a0<strong>\u041b\u044e\u0431\u043e\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u043c\u043e\u0436\u043d\u043e &#171;\u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c&#187; \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430<\/strong>\u00a0\u0438 \u043e\u043a\u0430\u0437\u0430\u0442\u044c\u0441\u044f \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0435. \u041d\u043e \u043e\u0431\u0440\u0430\u0442\u043d\u043e\u0435 \u043d\u0435\u0432\u0435\u0440\u043d\u043e, \u043d\u0435 \u0432\u0441\u0435 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u0438\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u0434\u0435\u0440\u0435\u0432\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0442 \u043a\u0430\u043a\u043e\u043c\u0443-\u0442\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0443, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0432\u0435\u0440\u0448\u0438\u043d\u044b \u043f\u043e\u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e \u043a\u0430\u043a \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0440\u0430\u0437\u0432\u0435\u0442\u0432\u0438\u0442\u044c \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b. \u041d\u0430 \u044d\u0442\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u0435 \u0442\u0430\u043a\u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u0440\u043e\u0432 \u043d\u0435\u0442. \u041d\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0439\u0442\u0435 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f &#171;abac&#187;. \u0412 \u043d\u0451\u043c \u0431\u0443\u0434\u0435\u0442 \u0432\u043d\u0443\u0442\u0440\u0435\u043d\u043d\u044f\u044f \u0432\u0435\u0440\u0448\u0438\u043d\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0435 &#171;a&#187;, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043d\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p>\u041f\u0443\u0442\u0438 &#171;ra-kadabra&#187; \u0438 &#171;bra-kadabra&#187; \u043c\u043e\u0436\u043d\u043e \u043a\u0430\u0436\u0434\u044b\u0439 &#171;\u0441\u0445\u043b\u043e\u043f\u043d\u0443\u0442\u044c&#187; \u0432 \u043e\u0434\u043d\u043e \u0440\u0435\u0431\u0440\u043e, \u0438 \u0433\u043e\u0432\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e \u0432\u0438\u0440\u0442\u0443\u0430\u043b\u044c\u043d\u0443\u044e \u0432\u0435\u0440\u0448\u0438\u043d\u0443 \u0432\u043d\u0443\u0442\u0440\u0438 \u0440\u0435\u0431\u0440\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0445\u0440\u0430\u043d\u0438\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441. <\/p>\n<p>\u0415\u0441\u0442\u044c <a href=\"https:\/\/brenden.github.io\/ukkonen-animation\/\" rel=\"noopener noreferrer nofollow\">\u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u0430\u044f \u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/a>  \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0430 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 &#171;\u043e\u0442 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c\u0443&#187;,  \u043e\u043d\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043d\u0430\u0438\u0432\u043d\u043e\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0432 \u043f\u043e\u0440\u044f\u0434\u043a\u0435 \u0443\u043c\u0435\u043d\u044c\u0448\u0435\u043d\u0438\u044f \u0434\u043b\u0438\u043d\u044b.<\/p>\n<h2>\u041d\u0430\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>\u041c\u043e\u0436\u043d\u043e \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0431\u0435 \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430. \u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u043c\u044b \u0438\u043c\u0435\u0435\u043c \u043f\u0440\u043e\u0441\u0442\u043e \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b \u2013 \u043a\u043e\u0440\u0435\u043d\u044c. \u041f\u043e\u0442\u043e\u043c, \u043d\u0430 \u0448\u0430\u0433\u0435 1, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0441\u043b\u043e\u0432\u043e abrakadabra. \u041f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u0441 \u044d\u0442\u0438\u043c \u0441\u043b\u043e\u0432\u043e\u043c \u0438 \u0435\u0449\u0451 \u043e\u0434\u0438\u043d \u0443\u0437\u0435\u043b. \u041d\u0430 \u0432\u0442\u043e\u0440\u043e\u043c \u0448\u0430\u0433\u0435 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0432\u0442\u043e\u0440\u043e\u0439 \u043f\u043e \u0434\u043b\u0438\u043d\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 brakadabra, \u0430 \u043d\u0430 \u0448\u0430\u0433\u0435 3 \u2013  \u0441\u0443\u0444\u0444\u0438\u043a\u0441 rakadabra. \u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e\u0435 \u043d\u0430\u0447\u0438\u043d\u0430\u0435\u0442\u0441\u044f \u043d\u0430 \u0448\u0430\u0433\u0435 4: \u043f\u0440\u0438 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0438 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 akadabra \u043c\u044b \u0432\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u0443 \u043d\u0430\u0441 \u0443\u0436\u0435 \u0435\u0441\u0442\u044c \u0440\u0435\u0431\u0440\u043e, \u043d\u0430\u0447\u0438\u043d\u0430\u044e\u0449\u0435\u0435\u0441\u044f \u043d\u0430 \u0431\u0443\u043a\u0432\u0443 &#8216;\u0430&#8217;, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u044b &#171;\u043f\u043e\u0439\u0434\u0451\u043c&#187; \u043f\u043e \u043d\u0435\u043c\u0443 \u0438 \u0440\u0430\u0437\u0432\u0435\u0442\u0432\u0438\u043c \u0435\u0433\u043e \u0432 \u043d\u0443\u0436\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u0435.<\/p>\n<figure class=\"full-width\"><figcaption><\/figcaption><\/figure>\n<p>\u0422\u0430\u043a \u043c\u044b \u0431\u0443\u0434\u0435\u043c \u043f\u043e\u0441\u0442\u0443\u043f\u0430\u0442\u044c, \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u044f \u043e\u0441\u0442\u0430\u0432\u0448\u0438\u0435\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b, \u0438 \u043f\u043e\u043b\u0443\u0447\u0438\u043c \u0434\u0435\u0440\u0435\u0432\u043e, \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0435 \u043d\u0430 \u043f\u0435\u0440\u0432\u043e\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 (\u043f\u0440\u043e\u0434\u0435\u043b\u0430\u0439\u0442\u0435 \u044d\u0442\u043e \u043f\u043e\u043b\u0435\u0437\u043d\u043e\u0435 \u0443\u043f\u0440\u0430\u0436\u043d\u0435\u043d\u0438\u0435, \u0435\u0449\u0451 \u0440\u0430\u0437 \u0441\u043c. <a href=\"https:\/\/brenden.github.io\/ukkonen-animation\/\" rel=\"noopener noreferrer nofollow\">\u0432\u0438\u0437\u0443\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044e<\/a>).<\/p>\n<p>\u041e\u043f\u0438\u0441\u0430\u043d\u043d\u044b\u0439 \u043d\u0430\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043a\u043e\u043d\u0441\u0442\u0440\u0443\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043d\u0435 \u0441\u0430\u043c\u044b\u0439 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439. \u041e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0439 \u0448\u0430\u0433 \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u0430 \u0434\u043b\u0438\u043d\u044b <em>n<\/em> \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0440\u0430\u0442\u0438\u0442\u044c \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0440\u044f\u0434\u043a\u0430 <em>n<\/em>, \u0441\u0430\u043c\u0438\u0445 \u0448\u0430\u0433\u043e\u0432 \u0442\u043e\u0436\u0435 <em>n<\/em>, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0433\u0440\u0443\u0431\u0430\u044f \u043e\u0446\u0435\u043d\u043a\u0430 \u0434\u0430\u0451\u0442 \u043e\u0446\u0435\u043d\u043a\u0443. \u041d\u043e \u043c\u0435\u0441\u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e  \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430, \u043e\u0446\u0435\u043d\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043a\u0430\u043a. \u042d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043d\u044f\u0442\u044c, \u0435\u0441\u043b\u0438 \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u043c \u0448\u0430\u0433\u0435 (\u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u0435 \u0435\u0449\u0451 \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430) \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0440\u0435\u0431\u0440\u043e \u0438 \u0443\u0437\u0435\u043b \u0438\u043b\u0438 \u043d\u0435 \u043f\u043e\u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f. \u041c\u0435\u0441\u0442\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0442\u0440\u0430\u0442\u0438\u0442\u0441\u044f \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0435 \u0440\u0435\u0431\u0440\u043e \u2013 \u044d\u0442\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u0434\u0432\u0430 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u043d\u0430\u0447\u0430\u043b\u0430 \u0438 \u043a\u043e\u043d\u0446\u0430 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0442\u0435\u043a\u0441\u0442\u0430. <\/p>\n<p>\u0422\u043e, \u0447\u0442\u043e \u0434\u0435\u0440\u0435\u0432\u043e \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u043c\u0435\u0441\u0442\u043e, \u0434\u0430\u0451\u0442 \u043d\u0430\u0434\u0435\u0436\u0434\u0443 \u043d\u0430 \u0442\u043e, \u0447\u0442\u043e \u0435\u0441\u0442\u044c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0433\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f.  \u0423\u0434\u0438\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0435\u0441\u0442\u044c, \u043c\u044b \u0440\u0430\u0437\u0431\u0435\u0440\u0451\u043c <a href=\"https:\/\/en.wikipedia.org\/wiki\/Ukkonen%27s_algorithm\" rel=\"noopener noreferrer nofollow\">\u0423\u043a\u043a\u043e\u043d\u0435\u043d\u0430<\/a>, \u043d\u043e \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0435\u043c, \u0437\u0430\u0447\u0435\u043c \u043d\u0443\u0436\u043d\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0435 \u0434\u0435\u0440\u0435\u0432\u043e.<\/p>\n<h2>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>ST \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u044b, \u043e\u043d\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0432\u0441\u0435 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u0418 \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043b\u0438 text \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 <em>x<\/em>,  \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u043f\u0440\u043e\u0441\u0442\u043e \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c &#171;\u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c&#187; \u0442\u0435\u043a\u0441\u0442 <em>x<\/em>, \u0434\u0432\u0438\u0433\u0430\u044f\u0441\u044c \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u043f\u043e \u0440\u0451\u0431\u0440\u0430\u043c, \u0438 \u0435\u0441\u043b\u0438 \u044d\u0442\u043e \u0443\u0434\u0430\u0451\u0442\u0441\u044f, \u0442\u043e \u0437\u043d\u0430\u0447\u0438\u0442 <em>x<\/em> \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u043e\u0439.<\/p>\n<p>\u0421 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430 \u043c\u043e\u0436\u043d\u043e \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0440\u0435\u0448\u0430\u0442\u044c \u0442\u0430\u043a\u0438\u0435 \u0437\u0430\u0434\u0430\u0447\u0438:<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 1: \u041f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c, \u0435\u0441\u0442\u044c \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 <em>x<\/em> \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 2: \u041d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u043e\u0431\u0449\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445 text1 \u0438 text2.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 3: \u041d\u0430\u0439\u0442\u0438 \u0441\u0430\u043c\u0443\u044e \u0434\u043b\u0438\u043d\u043d\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text \u0431\u043e\u043b\u0435\u0435 <em>k<\/em> \u0440\u0430\u0437.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 4: \u041d\u0430\u0439\u0442\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0434\u043b\u0438\u043d\u044b <em>k<\/em>, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u0441\u0442\u0440\u0435\u0447\u0430\u0435\u0442\u0441\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0440\u0430\u0437.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 5: \u041d\u0430\u0439\u0434\u0438\u0442\u0435 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u0442\u043e\u043f 10 \u043f\u043e \u0447\u0430\u0441\u0442\u043e\u0442\u0435 \u0441\u043b\u043e\u0432 \u0434\u043b\u0438\u043d\u044b <em>k<\/em> \u0438\u043b\u0438 \u0431\u043e\u043b\u044c\u0448\u0435.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 6: \u041d\u0430\u0439\u0442\u0438 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 text \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0435 <em>x<\/em>, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0435\u0441\u0442\u044c  \u043e\u0434\u0438\u043d \u0441\u0438\u043c\u0432\u043e\u043b &#8216;*&#8217;, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0439 \u043b\u044e\u0431\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0435,  \u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u043f\u0443\u0441\u0442\u043e\u0439.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0430 7:  \u0414\u0430\u043d\u0430 \u0431\u0430\u0437\u0430 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432. \u041d\u0430\u043f\u0438\u0448\u0438\u0442\u0435 \u0431\u044b\u0441\u0442\u0440\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u043e\u0442 \u0430\u0440\u0433\u0443\u043c\u0435\u043d\u0442\u0430 word, \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u044f\u044e\u0449\u0443\u044e \u0432 \u0441\u043b\u043e\u0432\u0435 word \u043e\u0434\u043d\u0443 \u0438\u043b\u0438 \u0434\u0432\u0435 \u043e\u043f\u0435\u0447\u0430\u0442\u043a\u0438 \u0442\u0438\u043f\u0430 &#171;\u0437\u0430\u043c\u0435\u043d\u0430 \u043e\u0434\u043d\u043e\u0439 \u0431\u0443\u043a\u0432\u044b \u043d\u0430 \u0434\u0440\u0443\u0433\u0443&#187;, &#171;\u0443\u0434\u0430\u043b\u0435\u043d\u0430 \u043e\u0434\u043d\u0430 \u0431\u0443\u043a\u0432\u0430&#187;, &#171;\u0432\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u0430 \u043e\u0434\u043d\u0430 \u043b\u0438\u0448\u043d\u044f\u044f \u0431\u0443\u043a\u0432\u0430&#187;. \u0424\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043e\u043b\u0436\u043d\u0430 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u0442\u044c 10 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u043e\u0432 \u0434\u043b\u044f \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043e\u043f\u0435\u0447\u0430\u0442\u043e\u043a, \u0435\u0441\u043b\u0438 \u0432\u0445\u043e\u0434\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e word \u043d\u0435\u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e\u0435. \u0414\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0430 \u0431\u044b\u0441\u0442\u0440\u043e, \u043c\u043e\u0436\u043d\u043e \u0438 \u043d\u0443\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u0443\u044e \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0443 \u0434\u0430\u043d\u043d\u044b\u0445 \u043d\u0430 \u0431\u0430\u0437\u0435 \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u044b\u0445 \u0441\u043b\u043e\u0432.<\/p>\n<p>\u0417\u0430\u0434\u0430\u0447\u0438 \u043a\u0430\u043a \u0431\u044b \u043f\u0440\u043e\u0441\u0442\u044b\u0435, \u043d\u043e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0443\u043c\u0435\u043d\u0438\u0438 \u0440\u0435\u0448\u0430\u0442\u044c \u0438\u0445 <strong>\u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f<\/strong> \u043e\u0442 \u0440\u0430\u0437\u043c\u0435\u0440\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445. \u0412\u0441\u0435 \u043e\u043d\u0438 \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0440\u0435\u0448\u0435\u043d\u044b \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e ST.  \u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0442\u0441\u044f \u0438\u0434\u0435\u0438 \u0442\u0438\u043f\u0430<\/p>\n<ul>\n<li>\n<p>\u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0432 \u0443\u0437\u043b\u0430\u0445 \u043a\u0430\u043a\u0438\u0435-\u0442\u043e \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0434\u0430\u043d\u043d\u044b\u0435 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u043b\u0443\u0431\u0438\u043d\u0443 \u0443\u0437\u043b\u0430 \u0432 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u0445, \u0438\u043b\u0438 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043b\u0438\u0441\u0442\u044c\u0435\u0432 \u0432 \u043f\u043e\u0434\u0434\u0435\u0440\u0435\u0432\u0435);<\/p>\n<\/li>\n<li>\n<p>\u043f\u0435\u0440\u0435\u0434 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0442\u044c \u0432 \u043a\u043e\u043d\u0435\u0446 \u0442\u0435\u043a\u0441\u0442\u0430 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b $;<\/p>\n<\/li>\n<li>\n<p>\u0434\u043b\u044f \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u043b\u043e\u0432 \u043c\u043e\u0436\u043d\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u0442\u044c ST \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043f\u043e\u043b\u0443\u0447\u0430\u0435\u0442\u0441\u044f \u0441\u043e\u0435\u0434\u0438\u043d\u0435\u043d\u0438\u0435\u043c \u0432\u0441\u0435\u0445 \u0441\u043b\u043e\u0432 \u0432 \u043e\u0434\u0438\u043d \u0442\u0435\u043a\u0441\u0442 \u0447\u0435\u0440\u0435\u0437 \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0437\u0434\u0435\u043b\u0438\u0442\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b $.<\/p>\n<\/li>\n<\/ul>\n<h2>\u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f  \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043d\u043e\u0433\u043e \u0434\u0435\u0440\u0435\u0432\u0430<\/h2>\n<p>\u0421\u0443\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 buld_tree \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0441\u0442\u0440\u043e\u0438\u0442\u0441\u044f \u0434\u0435\u0440\u0435\u0432\u043e \u0434\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u043e\u0432 &#171;a*&#187;, &#171;ab*&#187;, &#171;abr*&#187;, &#171;abra*&#187;, &#171;abrak*&#187;, &#8230; , \u0433\u0434\u0435 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0430 * \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442 &#171;\u0432\u0441\u0435 \u043e\u0441\u0442\u0430\u043b\u044c\u043d\u044b\u0435 \u0441\u043b\u0438\u043f\u0448\u0438\u0435\u0441\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u044b&#187;. \u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f\u00a0<strong>\u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0442\u043e\u0447\u043a\u043e\u0439<\/strong>:<\/p>\n<ul>\n<li>\n<p><em>n<\/em>\u00a0\u2013 \u043d\u043e\u043c\u0435\u0440 \u043d\u043e\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043f\u0435\u0440\u0435\u0434 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u043e\u0439 * , \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u0445\u043e\u0442\u0438\u043c \u0443\u0447\u0435\u0441\u0442\u044c \u0438, \u043a\u0430\u043a-\u0431\u044b, \u043e\u0442\u043e\u0440\u0432\u0430\u0442\u044c \u043e\u0442 \u0437\u0432\u0451\u0437\u0434\u043e\u0447\u043a\u0438 (\u0441\u043e\u0440\u0440\u0438, \u0440\u0430\u043d\u044c\u0448\u0435 n \u0431\u044b\u043b\u043e \u0440\u0430\u0432\u043d\u043e \u0434\u043b\u0438\u043d\u0435 \u0442\u0435\u043a\u0441\u0442\u0430, \u0442\u0435\u043f\u0435\u0440\u044c \u044d\u0442\u043e \u0438\u043d\u0434\u0435\u043a\u0441 \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c\u043e\u0439 \u0431\u0443\u043a\u0432\u044b) \u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c \u0434\u0435\u0440\u0435\u0432\u043e;<\/p>\n<\/li>\n<li>\n<p>node \u2013 \u0443\u0437\u0435\u043b \u0438\u0437 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043c\u044b \u0448\u0430\u0433\u0430\u0435\u043c \u0432 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442;<\/p>\n<\/li>\n<li>\n<p>edge \u2013 \u0440\u0435\u0431\u0440\u043e, \u043f\u043e \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043c\u044b \u0448\u0430\u0433\u0430\u0435\u043c; \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0430\u0440\u043e\u0439 \u0438\u043d\u0434\u0435\u043a\u0441\u043e\u0432 (first, last) \u0438 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0435 text[first: last];<\/p>\n<\/li>\n<li>\n<p>i \u2013 \u0438\u043d\u0434\u0435\u043a\u0441 \u0432\u043d\u0443\u0442\u0440\u0438 [first, last], \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u0434\u0430\u0451\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u044e \u043d\u0430 \u0440\u0435\u0431\u0440\u0435, \u0433\u0434\u0435 \u0438\u043c\u0435\u043d\u043d\u043e \u043c\u044b \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f.<\/p>\n<\/li>\n<\/ul>\n<p>\u0415\u0441\u0442\u044c \u0435\u0449\u0451 \u0441\u043a\u0440\u044b\u0442\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 j, \u0442\u0430\u043a\u043e\u0439, \u0447\u0442\u043e \u0442\u0435\u043a\u0441\u0442 text[j: first-1] \u043a\u0430\u043a \u0440\u0430\u0437 \u043f\u0440\u0438\u0432\u0451\u043b \u0431\u044b \u043d\u0430\u0441 \u0438\u0437 \u043a\u043e\u0440\u043d\u044f \u0434\u0435\u0440\u0435\u0432\u0430 \u0432 \u0432\u0435\u0440\u0448\u0438\u043d\u0443 node. \u0411\u0443\u0434\u0435\u043c \u044d\u0442\u043e\u0442 \u0444\u0430\u043a\u0442 \u0443\u0441\u043b\u043e\u0432\u043d\u043e \u0437\u0430\u043f\u0438\u0441\u044b\u0432\u0430\u0442\u044c \u0432 \u0432\u0438\u0434\u0435 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u0430<br \/>node = Node(text[j:first-1]).<\/p>\n<p>\u0412 \u043c\u0435\u0442\u043e\u0434\u0435 build_tree(node, n) \u0432\u043d\u0443\u0442\u0440\u0438 \u0446\u0438\u043a\u043b\u0430 while \u043c\u044b <em>\u043a\u0430\u043a \u0431\u044b<\/em> \u043d\u0430\u0445\u043e\u0434\u0438\u043c\u0441\u044f \u0432 \u0440\u0435\u0436\u0438\u043c\u0435 \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0434\u043e\u0431\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u043d\u0435\u043a\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 text[j:end] \u0432 \u0434\u0435\u0440\u0435\u0432\u043e \u0438 \u043c\u043e\u0434\u0438\u0444\u0438\u0446\u0438\u0440\u0443\u0435\u043c \u0434\u0435\u0440\u0435\u0432\u043e \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438.\u00a0<\/p>\n<p>\u0412 \u0434\u0430\u043d\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442 \u043c\u044b \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b\u0438 \u043e\u0442 \u043a\u043e\u0440\u043d\u044f \u0442\u0435\u043a\u0441\u0442 text[j:n] \u0438 \u0445\u043e\u0442\u0438\u043c \u0434\u0432\u0438\u0433\u0430\u0442\u044c\u0441\u044f \u0434\u0430\u043b\u044c\u0448\u0435, \u0430 \u0438\u043c\u0435\u043d\u043d\u043e, \u0445\u043e\u0442\u0438\u043c \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u0442\u044c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b text[n+1] \u043d\u0430 \u0440\u0435\u0431\u0440\u0435 edge. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c \u043d\u0430 1 \u043f\u0435\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0435 n \u0438 i \u0438 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0432\u0435\u0440\u043d\u043e \u043b\u0438, \u0447\u0442\u043e text[i] == text[n], \u0438 \u0435\u0441\u043b\u0438 \u0432\u0435\u0440\u043d\u043e, \u0442\u043e \u0434\u0432\u0438\u0433\u0430\u0435\u043c\u0441\u044f \u043f\u043e \u0440\u0435\u0431\u0440\u0443 \u0434\u0430\u043b\u044c\u0448\u0435. \u0412 \u043a\u0430\u043a\u043e\u0439-\u0442\u043e \u043c\u043e\u043c\u0435\u043d\u0442 \u0434\u0432\u0438\u0436\u0435\u043d\u0438\u0435 \u043f\u043e \u0440\u0435\u0431\u0440\u0443 \u043e\u0431\u0440\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u043e\u0432\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043d\u0435 \u0442\u043e\u0442: text[i] != text[n]. \u0418 \u0442\u043e\u0433\u0434\u0430 \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b <strong>\u0432\u0440\u0435\u0437\u0430\u0442\u044c \u0432 \u0440\u0435\u0431\u0440\u043e<\/strong> (\u0432\u00a0<strong>\u0430\u043a\u0442\u0438\u0432\u043d\u0443\u044e \u0442\u043e\u0447\u043a\u0443<\/strong>) <strong>\u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b<\/strong> \u0438 \u043e\u0442\u0432\u0435\u0442\u0432\u0438\u0442\u044c\u0441\u044f \u043e\u0442 \u043d\u0435\u0433\u043e \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u0435\u043c text[n: end].<\/p>\n<p>\u0418 \u0432\u043e\u0442 \u0441\u043b\u043e\u0436\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442: \u043a\u043e\u0433\u0434\u0430 \u043c\u044b, \u043f\u043e \u043c\u0435\u0440\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438, \u0441\u043e\u0437\u0434\u0430\u0451\u043c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b new_node=Node(text[j:n]), \u043c\u044b\u00a0<strong>\u0434\u0435\u043b\u0430\u0435\u043c \u0435\u0449\u0451 \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432<\/strong>\u00a0\u2013 \u043e\u0442\u0432\u043b\u0435\u043a\u0430\u0435\u043c\u0441\u044f \u043d\u0430 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0443 &#171;\u043f\u0440\u043e\u0439\u0442\u0438 \u043f\u0443\u0442\u044c text[first:n] \u0438\u0437 \u0443\u0437\u043b\u0430 Node(text[j+1:first-1]) \u0438 \u0442\u0430\u043c \u0442\u043e\u0436\u0435, \u0435\u0441\u043b\u0438 \u043d\u0443\u0436\u043d\u043e, \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b \u0438 \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0441\u0441\u044b\u043b\u043a\u0443 \u043d\u0430 \u043d\u0435\u0433\u043e&#187;.\u00a0<\/p>\n<p>\u0415\u0449\u0451 \u0440\u0430\u0437: \u0434\u0432\u0438\u0433\u0430\u044f\u0441\u044c \u0442\u0435\u043a\u0441\u0442\u043e\u043c text[n-k: n] \u0438\u0437 node=Node(text[j:first-1]) \u043f\u043e \u0440\u0435\u0431\u0440\u0443 text[first:last] \u0438 \u0432\u0441\u0442\u0440\u0435\u0442\u0438\u0432\u0448\u0438\u0441\u044c \u0441 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c\u044e \u0441\u043e\u0437\u0434\u0430\u0442\u044c \u043d\u043e\u0432\u044b\u0439 \u0443\u0437\u0435\u043b new_node=Node(text[j:n]), \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u0430\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u043c\u043e\u0436\u0435\u0442 \u0436\u0434\u0430\u0442\u044c \u043d\u0430\u0441 \u043d\u0430 \u043f\u0443\u0442\u0438 \u0438\u0437 suff_node=Node(text[j+1:first-1]), \u0435\u0441\u043b\u0438 \u043c\u044b \u043f\u043e\u0439\u0434\u0451\u043c \u0438\u0437 \u043d\u0435\u0433\u043e \u0442\u0435\u043c \u0436\u0435 \u0442\u0435\u043a\u0441\u0442\u043e\u043c text[n-k: n]. \u0418 \u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u044d\u0442\u043e\u0439 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438. \u041f\u0440\u0438 \u0440\u0435\u0448\u0435\u043d\u0438\u0438 \u044d\u0442\u043e\u0439 \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438, \u0432 \u0441\u0432\u043e\u044e \u043e\u0447\u0435\u0440\u0435\u0434\u044c, \u0442\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u0435\u0442 \u0441\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u0440\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u044b\u0439 \u0432\u044b\u0437\u043e\u0432 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0437\u0430\u0434\u0430\u0447\u0438 \u0443\u0436\u0435 \u0434\u043b\u044f \u0443\u0437\u043b\u0430 Node(text[j+2: first-1]) \u0438 \u0442\u0430\u043a \u0434\u0430\u043b\u0435\u0435.<\/p>\n<p>\u0412\u0430\u0436\u043d\u0430\u044f \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0430\u0446\u0438\u044f \u2013 \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0441\u043e\u0437\u0434\u0430\u0432\u0430\u0442\u044c \u0438<\/p>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-337283","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/337283","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=337283"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/337283\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=337283"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=337283"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=337283"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}