{"id":427321,"date":"2024-07-25T21:32:59","date_gmt":"2024-07-25T21:32:59","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=427321"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=427321","title":{"rendered":"<span>\u041a\u0430\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b KMP \u0438 Boyer-Moore \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0442 \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b<\/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><em>\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440!<\/em><\/p>\n<p>\u041f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b &#8212; <strong>\u0431\u0435\u0437 \u043d\u0438\u0445 \u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u043c\u0438\u0440,<\/strong> \u043e\u043d\u0438 \u043e\u0431\u043b\u0435\u0433\u0447\u0430\u044e\u0442 \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438 \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u043e\u043f\u044b\u0442. \u041e\u0434\u043d\u0430\u043a\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0441\u0442\u0440\u043e\u043a. \u041e\u0434\u043d\u0438 \u0438\u0437 \u043d\u0438\u0445 &#8212;  <em>Knuth-Morris-Pratt<\/em> \u0438 <em>Boyer-Moore<\/em>. <\/p>\n<p>\u0418\u0445 \u043c\u044b \u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0432 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e.<\/p>\n<h2>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Knuth-Morris-Pratt (KMP)<\/h2>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Knuth-Morris-Pratt<\/strong> \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0414\u043e\u043d\u0430\u043b\u044c\u0434\u043e\u043c \u041a\u043d\u0443\u0442\u043e\u043c, \u0414\u0436\u0435\u0439\u043c\u0441\u043e\u043c \u041c\u043e\u0440\u0440\u0438\u0441\u043e\u043c \u0438 \u0412\u043e\u043d\u043e\u043c \u041f\u0440\u0430\u0442\u0442\u043e\u043c \u0432 1977 \u0433\u043e\u0434\u0443. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0442\u0430\u043b \u0440\u0435\u0432\u043e\u043b\u044e\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0441\u0432\u043e\u0435\u0439 \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435. <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435. \u041e\u043d <strong>\u0440\u0435\u0448\u0430\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430<\/strong>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043f\u0443\u0442\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u041f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0441\u0442\u0440\u043e\u043a\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P \" alt=\"P \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/683\/b9a\/ee2\/683b9aee239eace0e05f2db265d80276.svg\" width=\"14\" height=\"17\"\/>\u0434\u043b\u0438\u043d\u044b <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/eee\/f88\/60f\/eeef8860fd832068eee6b3f844c843e1.svg\" width=\"17\" height=\"12\"\/> \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043c\u0430\u0441\u0441\u0438\u0432 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi\" alt=\"\\pi\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/02a\/26a\/63a\/02a26a63ab523f75413a0b8bfb7625bc.svg\" width=\"11\" height=\"12\"\/>, \u0433\u0434\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi[i]\" alt=\"\\pi[i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c3\/9e4\/81c\/4c39e481c8ccfb08579ba16f5c61ded6.svg\" width=\"28\" height=\"22\"\/> \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430 \u0441\u0442\u0440\u043e\u043a\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[0..i]\" alt=\"P[0..i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/702\/3a9\/a32\/7023a9a32d65b4cdf496c0fb770d3356.svg\" width=\"52\" height=\"22\"\/>, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a:<\/p>\n<ol>\n<li>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi[0] = 0\" alt=\"\\pi[0] = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3d2\/886\/897\/3d2886897b20b8d913b5dc21eecee2a0.svg\" width=\"67\" height=\"22\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[i] \" alt=\"P[i] \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9f2\/994\/724\/9f299472440950289b91f16420e6f7ed.svg\" width=\"32\" height=\"22\"\/>(\u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 1\" alt=\"i = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a01\/238\/235\/a0123823539001e63b8450c4772b990d.svg\" width=\"42\" height=\"16\"\/>): <\/p>\n<ul>\n<li>\n<p>\u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k = \\pi[i-1]\" alt=\"k = \\pi[i-1]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/087\/429\/752\/087429752cc5a85e3f14c0a6e82eed9e.svg\" width=\"97\" height=\"22\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043a\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k &gt; 0\" alt=\"k &gt; 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/296\/d92\/900\/296d929007f706d11dddfed70acb2d10.svg\" width=\"45\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[k] \\neq P[i]\" alt=\"P[k] \\neq P[i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b82\/729\/ba6\/b82729ba61a4736e0e4b91968ac76b7d.svg\" width=\"93\" height=\"22\"\/>, \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c5c\/38b\/e83\/c5c38be83b6088a34929c1a8d38c35a1.svg\" width=\"10\" height=\"17\"\/> \u0434\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi[k-1]\" alt=\"\\pi[k-1]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4f9\/e3c\/34e\/4f9e3c34e97bf1d9ca2c7b9265fec486.svg\" width=\"65\" height=\"22\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[k] == P[i]\" alt=\"P[k] == P[i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f2a\/3aa\/e52\/f2a3aae52588b652f396c0c581cc4148.svg\" width=\"108\" height=\"22\"\/>, \u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"k\" alt=\"k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/700\/6ef\/fa4\/7006effa489b3b8c5058583d69034f6f.svg\" width=\"10\" height=\"17\"\/> \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1\" alt=\"1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c0a\/a25\/2df\/c0aa252df64c406b3a14b66b0236492d.svg\" width=\"10\" height=\"16\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi[i] = k\" alt=\"\\pi[i] = k\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b4f\/333\/54f\/b4f33354fb398418fc6512a8442ff1eb.svg\" width=\"64\" height=\"22\"\/>.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, <strong>\u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u043d\u044f\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441 \u0435\u0451 \u043a\u043e\u043d\u0446\u043e\u043c.<\/strong><\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u0441\u0442\u0440\u043e\u043a\u0438 &#171;<em>ababaca<\/em>&#171;:<\/p>\n<ul>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[0] = a : \\pi[0] = 0\" alt=\"P[0] = a : \\pi[0] = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f45\/d2f\/963\/f45d2f963fd681c14516a99dbcb3d5c4.svg\" width=\"154\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[1] = b : \\pi[1] = 0\" alt=\"P[1] = b : \\pi[1] = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f7b\/931\/d87\/f7b931d873f2faba8a833dc220be3556.svg\" width=\"152\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[2] = a : \\pi[2] = 1\" alt=\"P[2] = a : \\pi[2] = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/6a5\/7a1\/b4f\/6a57a1b4fa3e35d82eaa15916121112c.svg\" width=\"154\" height=\"22\"\/>(\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;a&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;a&#187;)<\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[3] = b : \\pi[3] = 2 \" alt=\"P[3] = b : \\pi[3] = 2 \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/28c\/c5e\/01b\/28cc5e01b8facf9db79b5c912c0dafab.svg\" width=\"152\" height=\"22\"\/>(\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;ab&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;ab&#187;)<\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[4] = a : \\pi[4] = 3\" alt=\"P[4] = a : \\pi[4] = 3\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ac7\/76c\/33a\/ac776c33ae641876b9e4394deeb8bf79.svg\" width=\"154\" height=\"22\"\/> (\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;aba&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;aba&#187;)<\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[5] = c : \\pi[5] = 0\" alt=\"P[5] = c : \\pi[5] = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1cb\/2ec\/b61\/1cb2ecb61806a31ab4f7a100859aa96d.svg\" width=\"152\" height=\"22\"\/> (\u043d\u0435\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439)<\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[6] = a : \\pi[6] = 1\" alt=\"P[6] = a : \\pi[6] = 1\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f80\/a0c\/7ce\/f80a0c7ce5d1b1168fb7d3d740bc4d86.svg\" width=\"154\" height=\"22\"\/> (\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;a&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;a&#187;)<\/p>\n<\/li>\n<\/ul>\n<p><strong>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430<\/strong><\/p>\n<p>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0442\u0440\u043e\u043a\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P\" alt=\"P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/753\/cae\/7b9\/753cae7b9955a19b21c7c3eef4324271.svg\" width=\"14\" height=\"17\"\/> \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T\" alt=\"T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0c6\/d5c\/aa7\/0c6d5caa735cabdc42e9084db4ce9c43.svg\" width=\"14\" height=\"17\"\/> \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c:<\/p>\n<ol>\n<li>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 0\" alt=\"i = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/22d\/fe7\/8ef\/22dfe78ef66036e1371b3d583033f2b5.svg\" width=\"42\" height=\"16\"\/>\u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T\" alt=\"T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3f2\/14c\/6f1\/3f214c6f1b7ff8655b7a3af3e78ef9dc.svg\" width=\"14\" height=\"17\"\/>, <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" j = 0\" alt=\" j = 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f6b\/151\/514\/f6b1515149ac104db15ad2fc2e8f8cac.svg\" width=\"44\" height=\"19\"\/> \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P\" alt=\"P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fa5\/b13\/e7a\/fa5b13e7ac633147ef4951dd6a337e6c.svg\" width=\"14\" height=\"17\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c, \u043f\u043e\u043a\u0430<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" i &lt; n\" alt=\" i &lt; n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cb5\/88d\/180\/cb588d180ff505ce01acbb2d94d0c8d2.svg\" width=\"44\" height=\"16\"\/> \u0434\u043b\u0438\u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T\" alt=\"T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d88\/bcc\/1ca\/d88bcc1ca19689cfd7e5f009b904daad.svg\" width=\"14\" height=\"17\"\/>: <\/p>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[j] == T[i]\" alt=\"P[j] == T[i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ed0\/765\/f6b\/ed0765f6b90aea11f5d700a82ecc0e80.svg\" width=\"105\" height=\"22\"\/>, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cc3\/7a5\/ab3\/cc37a5ab35273b9d8cfc38661bda917c.svg\" width=\"7\" height=\"16\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"j\" alt=\"j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fb1\/0d9\/32d\/fb10d932de69aa09fb9fd3009b774302.svg\" width=\"8\" height=\"19\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"j == m\" alt=\"j == m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0ea\/264\/ca4\/0ea264ca43f13bad7bb19727fdb99324.svg\" width=\"66\" height=\"19\"\/> <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\u0434\u043b\u0438\u043d\u0430 P\" alt=\"\u0434\u043b\u0438\u043d\u0430 P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cd2\/980\/9a4\/cd29809a4b93d0e00e371ef9a1a77633.svg\" width=\"62\" height=\"25\"\/>, \u0437\u043d\u0430\u0447\u0438\u0442, \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435: <\/p>\n<ul>\n<li>\n<p>\u041f\u043e\u0437\u0438\u0446\u0438\u044f \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f:<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" i - j\" alt=\" i - j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/29a\/2b4\/6bc\/29a2b46bccc8515ba3b4f4130501042c.svg\" width=\"38\" height=\"19\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0421\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"j\" alt=\"j\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e0a\/b79\/688\/e0ab7968801a804e920b7cce5d953927.svg\" width=\"8\" height=\"19\"\/> \u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"\\pi[j-1]\" alt=\"\\pi[j-1]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0d6\/457\/4d4\/0d64574d4c206513f013dc839fa3fc20.svg\" width=\"63\" height=\"22\"\/> \u0434\u043b\u044f \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P[j] \\neq T[i]\" alt=\"P[j] \\neq T[i]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/359\/d69\/d85\/359d69d85c6a51daa7d2bbd9766f6734.svg\" width=\"90\" height=\"22\"\/>: <\/p>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 j \\neq 0, \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" j = \\pi[j-1]\" alt=\" j = \\pi[j-1]\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c3\/810\/41b\/4c381041bb5faf2bc4a3e22a7b0de6a5.svg\" width=\"97\" height=\"22\"\/>.<\/p>\n<\/li>\n<li>\n<p>\u0418\u043d\u0430\u0447\u0435, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i\" alt=\"i\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a1f\/9fa\/472\/a1f9fa472b0a2676f46097e477df6705.svg\" width=\"7\" height=\"16\"\/>.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c KMP \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440<\/h4>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u0434\u0435 \u043c\u044b \u0438\u0449\u0435\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 &#171;<em>ababaca<\/em>&#187; \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 &#171;<em>bacbabababacaca<\/em>&#171;:<\/p>\n<ol>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f &#171;<em>ababaca<\/em>&#171;: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"0, 0, 1, 2, 3, 0, 1.\" alt=\"0, 0, 1, 2, 3, 0, 1.\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d92\/dde\/36f\/d92dde36f1db84876801fd727f85db33.svg\" width=\"124\" height=\"19\"\/><\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430: <\/p>\n<ul>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 0, j = 0 : &quot;b&quot; != &quot;a&quot;, ( i++ ).\" alt=\"i = 0, j = 0 : &quot;b&quot; != &quot;a&quot;, ( i++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/a77\/a44\/2de\/a77a442def1f2f432efd6c8492040001.svg\" width=\"283\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 1, j = 0 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" alt=\"i = 1, j = 0 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0b8\/72c\/727\/0b872c727a05d83fac4dd9dc9e405183.svg\" width=\"344\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 2, j = 1 : &quot;c&quot; != &quot;b&quot;, ( j = 0 ), ( i++ ).\" alt=\"i = 2, j = 1 : &quot;c&quot; != &quot;b&quot;, ( j = 0 ), ( i++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/102\/aa8\/39f\/102aa839f941d3394ddb9d6bc9c0c017.svg\" width=\"348\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 3, j = 0 : &quot;b&quot; != &quot;a&quot;, ( i++ ).\" alt=\"i = 3, j = 0 : &quot;b&quot; != &quot;a&quot;, ( i++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/425\/4a7\/028\/4254a7028f63e26f6a59c10c49f01902.svg\" width=\"283\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 4, j = 0 ): &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" alt=\"i = 4, j = 0 ): &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/935\/1d2\/b3b\/9351d2b3b09f58528249a88fdf1ce543.svg\" width=\"352\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 5, j = 1 : &quot;b&quot; == &quot;b&quot;, ( i++, j++ ).\" alt=\"i = 5, j = 1 : &quot;b&quot; == &quot;b&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/f22\/c82\/ad2\/f22c82ad2279acb8b44333609b79aad9.svg\" width=\"340\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 6, j = 2 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" alt=\"i = 6, j = 2 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c91\/4cb\/9ca\/c914cb9ca6b71a53c815aae143480c16.svg\" width=\"344\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 7, j = 3 : &quot;b&quot; == &quot;b&quot;, ( i++, j++ ).\" alt=\"i = 7, j = 3 : &quot;b&quot; == &quot;b&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/4c8\/c0a\/d5e\/4c8c0ad5e60e95fed6dd407178883420.svg\" width=\"340\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 8, j = 4 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" alt=\"i = 8, j = 4 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/3ee\/1c7\/701\/3ee1c7701ec2853a2247d7095f97e6ec.svg\" width=\"344\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 9, j = 5 : &quot;c&quot; == &quot;c&quot;, ( i++, j++ ).\" alt=\"i = 9, j = 5 : &quot;c&quot; == &quot;c&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/fca\/152\/7da\/fca1527da1278fbd0c0166b87c659e66.svg\" width=\"341\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i = 10, j = 6 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" alt=\"i = 10, j = 6 : &quot;a&quot; == &quot;a&quot;, ( i++, j++ ).\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e5d\/939\/20e\/e5d93920e3962b6cb1cb4bb23193c049.svg\" width=\"354\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"j = 7 \" alt=\"j = 7 \" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/0be\/d0b\/a9d\/0bed0ba9d7358dbcc39a48d009e0f129.svg\" width=\"44\" height=\"20\"\/>: \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438  <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"i - j = 10 - 7 = 3 .\" alt=\"i - j = 10 - 7 = 3 .\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9a2\/10e\/334\/9a210e334f0c4ae1ed2eb28c9e513385.svg\" width=\"157\" height=\"20\"\/><\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043a\u043e\u0434\u0435<\/h4>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435:<\/p>\n<pre><code class=\"python\">def kmp_search(pattern, text):     def compute_prefix_function(pattern):         m = len(pattern)         pi = [0] * m         k = 0          for q in range(1, m):             while k &gt; 0 and pattern[k] != pattern[q]:                 k = pi[k - 1]             if pattern[k] == pattern[q]:                 k += 1             pi[q] = k          return pi      n = len(text)     m = len(pattern)     pi = compute_prefix_function(pattern)     q = 0      for i in range(n):         while q &gt; 0 and pattern[q] != text[i]:             q = pi[q - 1]         if pattern[q] == text[i]:             q += 1         if q == m:             print(f\"Pattern occurs at index {i - m + 1}\")             q = pi[q - 1]  # \u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f text = \"ABC ABCDAB ABCDABCDABDE\" pattern = \"ABCDABD\" kmp_search(pattern, text)<\/code><\/pre>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>compute_prefix_function(pattern)<\/code> \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u041f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p><code>pi<\/code> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438.<\/p>\n<p><code>k<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0435\u0433\u043e \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p><strong>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>kmp_search(pattern, text)<\/code>: <\/p>\n<p><code>n<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0442\u0435\u043a\u0441\u0442\u0430, <code>m<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e <code>compute_prefix_function<\/code>.<\/p>\n<p><code>q<\/code> &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0441 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u043b\u0438 \u043e\u043d \u0441 \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435. \u0415\u0441\u043b\u0438 \u0434\u0430, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c <code>q<\/code>. \u0415\u0441\u043b\u0438 <code>q<\/code> \u0440\u0430\u0432\u043d\u043e \u0434\u043b\u0438\u043d\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u0437\u043d\u0430\u0447\u0438\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0438 \u043f\u0435\u0447\u0430\u0442\u0430\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f \u0432 \u0442\u0435\u043a\u0441\u0442\u0435. \u0417\u0430\u0442\u0435\u043c \u0441\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u043c <code>q<\/code> \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a.<\/p>\n<p>\u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443.<\/p>\n<h2>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore<\/h2>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore<\/strong> \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0420\u043e\u0431\u0435\u0440\u0442\u043e\u043c \u0411\u043e\u0439\u0435\u0440\u043e\u043c \u0438 \u0414\u0436\u0435\u0439\u043e\u043c \u041c\u0443\u0440\u043e\u043c \u0442\u0430\u043a\u0436\u0435 \u0432 1977 \u0433\u043e\u0434\u0443. <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c <strong>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0432\u0435 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438<\/strong> \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430: \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430. \u042d\u0442\u0438 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0447\u0430\u0441\u0442\u0438 \u0441\u0442\u0440\u043e\u043a\u0438 \u043f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438.<\/p>\n<h4>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430<\/h4>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043e \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0441 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0435 \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0441\u0442\u0440\u043e\u043a\u0438, \u0430 \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0438\u0445 \u0441\u043d\u043e\u0432\u0430.<\/p>\n<p><strong>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0421\u043e\u0437\u0434\u0430\u0451\u0442\u0441\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P\" alt=\"P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/e06\/bde\/f2e\/e06bdef2efc1b0ef61c6accbd5b17569.svg\" width=\"14\" height=\"17\"\/>. \u042d\u0442\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0441 \u0443\u0447\u0451\u0442\u043e\u043c \u0435\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0412\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0438\u0441\u043a\u0430, \u0435\u0441\u043b\u0438 \u0441\u0438\u043c\u0432\u043e\u043b \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T\" alt=\"T\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/8db\/26d\/403\/8db26d403bfa48b3861a8442d34dd00e.svg\" width=\"14\" height=\"17\"\/> \u043d\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435 P, \u0448\u0430\u0431\u043b\u043e\u043d \u0441\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0432\u043f\u0430\u043b \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u044d\u0442\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435.<\/p>\n<\/li>\n<\/ol>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<p>\u041f\u0443\u0441\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P = &quot;EXAMPLE&quot;\" alt=\"P = &quot;EXAMPLE&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c4b\/0e4\/ae9\/c4b0e4ae9b4155b76ccee0239aa0308e.svg\" width=\"173\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T = &quot;HERE IS A SIMPLE EXAMPLE&quot;\" alt=\"T = &quot;HERE IS A SIMPLE EXAMPLE&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/089\/4ec\/ecc\/0894ececc22438fe9795b076caba12e0.svg\" width=\"355\" height=\"17\"\/>.<\/p>\n<p>\u041f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u043c \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"I\" alt=\"I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/22f\/004\/710\/22f004710925f510178ee5655a63a3d1.svg\" width=\"10\" height=\"17\"\/> \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"E\" alt=\"E\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/2cc\/921\/785\/2cc921785f4bdbe65b381238a6f8f58d.svg\" width=\"15\" height=\"17\"\/>\u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0432\u0438\u0434\u0438\u0442, \u0447\u0442\u043e <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"I\" alt=\"I\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/c6c\/11f\/d1d\/c6c11fd1d41b61213432e218b11d277e.svg\" width=\"10\" height=\"17\"\/> \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435. \u0422\u043e\u0433\u0434\u0430 \u0448\u0430\u0431\u043b\u043e\u043d \u0441\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u043b \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<h4>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430<\/h4>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430\u043c\u0438. \u041a\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430\u0445 \u0434\u043b\u044f \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<p><strong>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0421\u043e\u0437\u0434\u0430\u0451\u0442\u0441\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P\" alt=\"P\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/65d\/094\/2a5\/65d0942a5e497b7a34c4d2077129368c.svg\" width=\"14\" height=\"17\"\/>. \u042d\u0442\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0447\u0430\u0441\u0442\u044c \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0441\u043e\u0432\u043f\u0430\u043b\u0430 \u0441 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438, \u043d\u043e \u0434\u0430\u043b\u0435\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u0435\u0449\u0430\u0435\u0442 \u0448\u0430\u0431\u043b\u043e\u043d \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0432\u044b\u0440\u043e\u0432\u043d\u044f\u043b\u0441\u044f \u0441 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<\/li>\n<\/ol>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<p>\u041f\u0443\u0441\u0442\u044c<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\" P = &quot;ABCDABD&quot;\" alt=\" P = &quot;ABCDABD&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/b49\/ffb\/fff\/b49ffbfff268a314b8b2e01ce3bbeb19.svg\" width=\"170\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T = &quot;ABC ABCDAB ABCDABCDABDE&quot;\" alt=\"T = &quot;ABC ABCDAB ABCDABCDABDE&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d36\/30a\/3c5\/d3630a3c5c32cbcf03312f17f196292d.svg\" width=\"376\" height=\"17\"\/>.<\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"E\" alt=\"E\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/9c9\/4ba\/91a\/9c94ba91a3f0d73aeb940eccfb5fe00a.svg\" width=\"15\" height=\"17\"\/> \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"D\" alt=\"D\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/d00\/b9c\/9f3\/d00b9c9f35dcdf8963cbd32e9f1c593e.svg\" width=\"16\" height=\"17\"\/> \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u043d\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442, \u0447\u0442\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043f\u043e\u0437\u0438\u0446\u0438\u0435\u0439 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0448\u0430\u0431\u043b\u043e\u043d \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u0432\u043f\u0440\u0430\u0432\u043e.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f<\/h4>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0442\u0440\u043e\u043a\u0443 T \u0438 \u0448\u0430\u0431\u043b\u043e\u043d P:<\/p>\n<ul>\n<li>\n<p><strong>\u0428\u0430\u0433 1:<\/strong> \u0412\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0441 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 2:<\/strong> \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0441 \u043a\u043e\u043d\u0446\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 3:<\/strong> \u041f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438\u043b\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 4:<\/strong> \u0421\u043c\u0435\u0449\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440:<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"P = &quot;ABCDABD&quot;\" alt=\"P = &quot;ABCDABD&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/ac2\/874\/0fe\/ac28740fe6dd93afab7f400106e11f01.svg\" width=\"170\" height=\"17\"\/> \u0438 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"T = &quot;ABC ABCDAB ABCDABCDABDE&quot;\" alt=\"T = &quot;ABC ABCDAB ABCDABCDABDE&quot;\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/18b\/57e\/c18\/18b57ec182f951f1d36e5e26b447816c.svg\" width=\"376\" height=\"17\"\/>.<\/p>\n<ol>\n<li>\n<p><strong>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f:<\/strong><\/p>\n<ul>\n<li>\n<p>\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432: &#8216;<img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"A': 6, 'B': 5, 'C': 4, 'D': 3, 'E': 1, 'L': 0\" alt=\"A': 6, 'B': 5, 'C': 4, 'D': 3, 'E': 1, 'L': 0\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/cce\/409\/5e9\/cce4095e95f8e8946e87ec760ac75aff.svg\" width=\"348\" height=\"22\"\/><\/p>\n<\/li>\n<li>\n<p>\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432: <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"1, 1, 1, 4, 4, 4, 7\" alt=\"1, 1, 1, 4, 4, 4, 7\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/338\/b35\/b03\/338b35b031f9daf130fde21a812ba910.svg\" width=\"119\" height=\"20\"\/><\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p><strong>\u041f\u043e\u0438\u0441\u043a:<\/strong><\/p>\n<ul>\n<li>\n<p>\u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0441\u0442\u0440\u043e\u043a\u0443 \u0438 \u0448\u0430\u0431\u043b\u043e\u043d.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0435 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u043f\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0430\u043c.<\/p>\n<\/li>\n<li>\n<p>\u0421\u043c\u0435\u0449\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore \u0438\u043c\u0435\u0435\u0442 \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"O(n\/m)\" alt=\"O(n\/m)\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/390\/e2f\/20b\/390e2f20bb7d674c36d2c8f4f2ce3d9b.svg\" width=\"68\" height=\"22\"\/> \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u0433\u0434\u0435 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"n\" alt=\"n\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/1d1\/bbd\/863\/1d1bbd863f7132750a1585027fddc0ad.svg\" width=\"12\" height=\"12\"\/> \u2014 \u0434\u043b\u0438\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0438, \u0430 <img loading=\"lazy\" decoding=\"async\" class=\"formula inline\" source=\"m\" alt=\"m\" src=\"https:\/\/habrastorage.org\/getpro\/habr\/upload_files\/825\/e63\/8fb\/825e638fb3ec8fe9df91017355ae20c8.svg\" width=\"17\" height=\"12\"\/> \u2014 \u0434\u043b\u0438\u043d\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448 \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u043c\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c\u0438.<\/p>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0434\u0430:<\/strong><\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435:<\/p>\n<pre><code class=\"python\">def boyer_moore_search(pattern, text):     def bad_character_table(pattern):         table = {}         m = len(pattern)         for i in range(m - 1):             table[pattern[i]] = i         return table      def good_suffix_table(pattern):         m = len(pattern)         table = [0] * m         last_prefix_position = m          for i in range(m - 1, -1, -1):             if is_prefix(pattern, i + 1):                 last_prefix_position = i + 1             table[m - 1 - i] = last_prefix_position - i + m - 1          for i in range(m - 1):             slen = suffix_length(pattern, i)             table[slen] = m - 1 - i + slen          return table      def is_prefix(pattern, p):         m = len(pattern)         for i in range(p, m):             if pattern[i] != pattern[i - p]:                 return False         return True      def suffix_length(pattern, p):         m = len(pattern)         length = 0         i = p         j = m - 1         while i &gt;= 0 and pattern[i] == pattern[j]:             length += 1             i -= 1             j -= 1         return length      n = len(text)     m = len(pattern)     if m == 0:         return []      bad_char_table = bad_character_table(pattern)     good_suffix_table = good_suffix_table(pattern)      s = 0     while s &lt;= n - m:         j = m - 1         while j &gt;= 0 and pattern[j] == text[s + j]:             j -= 1         if j &lt; 0:             print(f\"Pattern occurs at index {s}\")             s += good_suffix_table[0]         else:             bad_char_shift = j - bad_char_table.get(text[s + j], -1)             good_suffix_shift = good_suffix_table[j]             s += max(bad_char_shift, good_suffix_shift)  # \u043f\u0440\u0438\u043c\u0435\u0440 text = \"HERE IS A SIMPLE EXAMPLE\" pattern = \"EXAMPLE\" boyer_moore_search(pattern, text)<\/code><\/pre>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>bad_character_table(pattern)<\/code> \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u043a\u0440\u043e\u043c\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430.<\/p>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>good_suffix_table(pattern)<\/code> \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p><strong>\u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <\/strong><code>is_prefix(pattern, p)<\/code> \u0438 <code>suffix_length(pattern, p)<\/code>:<\/p>\n<p><code>is_prefix<\/code> \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043e\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 <code>p<\/code> \u0434\u043e \u043a\u043e\u043d\u0446\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u043c \u0432\u0441\u0435\u0433\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p><code>suffix_length<\/code> \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 <code>p<\/code>.<\/p>\n<p><strong>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>boyer_moore_search(pattern, text)<\/code>\u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u041f\u043e\u0441\u043b\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u0431\u0435 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0434\u043b\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f\u0445. \u0410 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0439 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435.<\/p>\n<hr\/>\n<p>\u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u0438\u044c, \u044d\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u0447\u0435\u043d\u044c \u043c\u043e\u0449\u043d\u044b\u0435 \u0438 \u043a\u0430\u0436\u0434\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0438 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u0430. <\/p>\n<p>KMP \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435\u043c \u043f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f\u0445, \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435. <\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0432\u0435 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438: \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 \u0437\u0430 \u0441\u0447\u0451\u0442 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<p>\u0412\u044b\u0431\u043e\u0440 \u043c\u0435\u0436\u0434\u0443 KMP \u0438 Boyer-Moore \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. <\/p>\n<blockquote>\n<p>\u0420\u0430\u0437\u0432\u0438\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043c\u044b\u0448\u043b\u0435\u043d\u0438\u0435 \u0438 \u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/otus.pw\/NYeK\/\">\u043d\u0430 \u043e\u043d\u043b\u0430\u0439\u043d-\u043a\u0443\u0440\u0441\u0435 \u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445\u00bb<\/a> \u0432 \u041e\u0442\u0443\u0441.<\/p>\n<\/blockquote>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/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\/articles\/828572\/\"> https:\/\/habr.com\/ru\/articles\/828572\/<\/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><em>\u041f\u0440\u0438\u0432\u0435\u0442, \u0425\u0430\u0431\u0440!<\/em><\/p>\n<p>\u041f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0435 \u0441\u0438\u0441\u0442\u0435\u043c\u044b &#8212; <strong>\u0431\u0435\u0437 \u043d\u0438\u0445 \u043d\u0435 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u0438\u0442\u044c \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0438\u0439 \u043c\u0438\u0440,<\/strong> \u043e\u043d\u0438 \u043e\u0431\u043b\u0435\u0433\u0447\u0430\u044e\u0442 \u0434\u043e\u0441\u0442\u0443\u043f \u043a \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 \u0438 \u0443\u043b\u0443\u0447\u0448\u0430\u044e\u0442 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0438\u0439 \u043e\u043f\u044b\u0442. \u041e\u0434\u043d\u0430\u043a\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u0430\u044f \u0441\u0438\u0441\u0442\u0435\u043c\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u043b\u0430 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e, \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0434\u043b\u044f \u043e\u0431\u0440\u0430\u0431\u043e\u0442\u043a\u0438 \u0441\u0442\u0440\u043e\u043a. \u041e\u0434\u043d\u0438 \u0438\u0437 \u043d\u0438\u0445 &#8212;  <em>Knuth-Morris-Pratt<\/em> \u0438 <em>Boyer-Moore<\/em>. <\/p>\n<p>\u0418\u0445 \u043c\u044b \u0438 \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0432 \u0441\u0435\u0433\u043e\u0434\u043d\u044f\u0448\u043d\u0435\u0439 \u0441\u0442\u0430\u0442\u044c\u0435, \u043d\u0430\u0447\u043d\u0435\u043c \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e.<\/p>\n<h2>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Knuth-Morris-Pratt (KMP)<\/h2>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Knuth-Morris-Pratt<\/strong> \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0414\u043e\u043d\u0430\u043b\u044c\u0434\u043e\u043c \u041a\u043d\u0443\u0442\u043e\u043c, \u0414\u0436\u0435\u0439\u043c\u0441\u043e\u043c \u041c\u043e\u0440\u0440\u0438\u0441\u043e\u043c \u0438 \u0412\u043e\u043d\u043e\u043c \u041f\u0440\u0430\u0442\u0442\u043e\u043c \u0432 1977 \u0433\u043e\u0434\u0443. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u0442\u0430\u043b \u0440\u0435\u0432\u043e\u043b\u044e\u0446\u0438\u043e\u043d\u043d\u044b\u043c \u0431\u043b\u0430\u0433\u043e\u0434\u0430\u0440\u044f \u0441\u0432\u043e\u0435\u0439 \u0441\u043f\u043e\u0441\u043e\u0431\u043d\u043e\u0441\u0442\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0442\u044c \u043f\u043e\u0438\u0441\u043a \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435. <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0435\u0434\u043d\u0430\u0437\u043d\u0430\u0447\u0435\u043d \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435. \u041e\u043d <strong>\u0440\u0435\u0448\u0430\u0435\u0442 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0443 \u043d\u0430\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430<\/strong>, \u043f\u0440\u0438 \u043a\u043e\u0442\u043e\u0440\u043e\u043c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u044b\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u0438\u0445 \u0438 \u0442\u0435\u0445 \u0436\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043f\u0443\u0442\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0440\u0435\u0434\u0432\u0430\u0440\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0441\u0441\u0447\u0438\u0442\u0430\u043d\u043d\u043e\u0439 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438. \u041f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0434\u043b\u044f \u0441\u0442\u0440\u043e\u043a\u0438 \u0434\u043b\u0438\u043d\u044b  \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043c\u0430\u0441\u0441\u0438\u0432 , \u0433\u0434\u0435  \u0443\u043a\u0430\u0437\u044b\u0432\u0430\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430 \u0441\u0442\u0440\u043e\u043a\u0438 , \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c \u044d\u0442\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<p>\u041f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0430\u043a:<\/p>\n<ol>\n<li>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f: .<\/p>\n<\/li>\n<li>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 (\u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 ): <\/p>\n<ul>\n<li>\n<p>\u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c .<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u043a\u0430  \u0438 , \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u043c  \u0434\u043e .<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 , \u0442\u043e  \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u043d\u0430 .<\/p>\n<\/li>\n<li>\n<p>\u0423\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c .<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, <strong>\u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u043f\u043e\u043d\u044f\u0442\u044c, \u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438\u0437 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0442 \u0441 \u0435\u0451 \u043a\u043e\u043d\u0446\u043e\u043c.<\/strong><\/p>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u0441\u0442\u0440\u043e\u043a\u0438 &#171;<em>ababaca<\/em>&#171;:<\/p>\n<ul>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<p>(\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;a&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;a&#187;)<\/p>\n<\/li>\n<li>\n<p>(\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;ab&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;ab&#187;)<\/p>\n<\/li>\n<li>\n<p> (\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;aba&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;aba&#187;)<\/p>\n<\/li>\n<li>\n<p> (\u043d\u0435\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439)<\/p>\n<\/li>\n<li>\n<p> (\u043f\u0440\u0435\u0444\u0438\u043a\u0441 &#171;a&#187; \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c &#171;a&#187;)<\/p>\n<\/li>\n<\/ul>\n<p><strong>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430<\/strong><\/p>\n<p>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0442\u0440\u043e\u043a\u0438  \u0432 \u0441\u0442\u0440\u043e\u043a\u0435  \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c:<\/p>\n<ol>\n<li>\n<p>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f: \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f ,  \u0438\u043d\u0434\u0435\u043a\u0441 \u0434\u043b\u044f .<\/p>\n<\/li>\n<li>\n<p>\u041f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c, \u043f\u043e\u043a\u0430 \u0434\u043b\u0438\u043d\u0430 : <\/p>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 , \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c  \u0438 .<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438  , \u0437\u043d\u0430\u0447\u0438\u0442, \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435: <\/p>\n<ul>\n<li>\n<p>\u041f\u043e\u0437\u0438\u0446\u0438\u044f \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f:.<\/p>\n<\/li>\n<li>\n<p>\u0421\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u043c  \u043d\u0430  \u0434\u043b\u044f \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0435\u043d\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 : <\/p>\n<ul>\n<li>\n<p>\u0415\u0441\u043b\u0438 j \\neq 0, \u0443\u0441\u0442\u0430\u043d\u0430\u0432\u043b\u0438\u0432\u0430\u0435\u043c.<\/p>\n<\/li>\n<li>\n<p>\u0418\u043d\u0430\u0447\u0435, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c .<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c KMP \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e, \u0447\u0442\u043e\u0431\u044b \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u043f\u043e\u0432\u0442\u043e\u0440\u043d\u044b\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440<\/h4>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u0438\u043c\u0435\u0440, \u0433\u0434\u0435 \u043c\u044b \u0438\u0449\u0435\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 &#171;<em>ababaca<\/em>&#187; \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 &#171;<em>bacbabababacaca<\/em>&#171;:<\/p>\n<ol>\n<li>\n<p>\u041d\u0430\u0445\u043e\u0434\u0438\u043c \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f &#171;<em>ababaca<\/em>&#171;: <\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430: <\/p>\n<ul>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<\/li>\n<li>\n<p>: \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438  <\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 \u0432 \u043a\u043e\u0434\u0435<\/h4>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435:<\/p>\n<pre><code class=\"python\">def kmp_search(pattern, text):     def compute_prefix_function(pattern):         m = len(pattern)         pi = [0] * m         k = 0          for q in range(1, m):             while k &gt; 0 and pattern[k] != pattern[q]:                 k = pi[k - 1]             if pattern[k] == pattern[q]:                 k += 1             pi[q] = k          return pi      n = len(text)     m = len(pattern)     pi = compute_prefix_function(pattern)     q = 0      for i in range(n):         while q &gt; 0 and pattern[q] != text[i]:             q = pi[q - 1]         if pattern[q] == text[i]:             q += 1         if q == m:             print(f\"Pattern occurs at index {i - m + 1}\")             q = pi[q - 1]  # \u043f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f text = \"ABC ABCDAB ABCDABCDABDE\" pattern = \"ABCDABD\" kmp_search(pattern, text)<\/code><\/pre>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>compute_prefix_function(pattern)<\/code> \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u041f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0438\u043d\u0434\u0435\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u043e\u0431\u0441\u0442\u0432\u0435\u043d\u043d\u043e\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0442\u0430\u043a\u0436\u0435 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p><code>pi<\/code> &#8212; \u043c\u0430\u0441\u0441\u0438\u0432, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0439 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438.<\/p>\n<p><code>k<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0433\u043e \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u0430, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0435\u0433\u043e \u0441 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u043c.<\/p>\n<p><strong>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>kmp_search(pattern, text)<\/code>: <\/p>\n<p><code>n<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0442\u0435\u043a\u0441\u0442\u0430, <code>m<\/code> &#8212; \u0434\u043b\u0438\u043d\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p>\u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e <code>compute_prefix_function<\/code>.<\/p>\n<p><code>q<\/code> &#8212; \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0441 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p>\u0414\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0442\u0435\u043a\u0441\u0442\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u043b\u0438 \u043e\u043d \u0441 \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435. \u0415\u0441\u043b\u0438 \u0434\u0430, \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0435\u043c <code>q<\/code>. \u0415\u0441\u043b\u0438 <code>q<\/code> \u0440\u0430\u0432\u043d\u043e \u0434\u043b\u0438\u043d\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u0437\u043d\u0430\u0447\u0438\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0438 \u043f\u0435\u0447\u0430\u0442\u0430\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u043d\u0430\u0447\u0430\u043b\u0430 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f \u0432 \u0442\u0435\u043a\u0441\u0442\u0435. \u0417\u0430\u0442\u0435\u043c \u0441\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u043c <code>q<\/code> \u043d\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0438\u0437 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u0438, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0438\u0442\u044c \u043f\u043e\u0438\u0441\u043a.<\/p>\n<p>\u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443.<\/p>\n<h2>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore<\/h2>\n<p><strong>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore<\/strong> \u0431\u044b\u043b \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u043d \u0420\u043e\u0431\u0435\u0440\u0442\u043e\u043c \u0411\u043e\u0439\u0435\u0440\u043e\u043c \u0438 \u0414\u0436\u0435\u0439\u043e\u043c \u041c\u0443\u0440\u043e\u043c \u0442\u0430\u043a\u0436\u0435 \u0432 1977 \u0433\u043e\u0434\u0443. <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c <strong>\u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0432\u0435 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438<\/strong> \u0434\u043b\u044f \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f \u043f\u043e\u0438\u0441\u043a\u0430: \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430. \u042d\u0442\u0438 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u0447\u0430\u0441\u0442\u0438 \u0441\u0442\u0440\u043e\u043a\u0438 \u043f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438.<\/p>\n<h4>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430<\/h4>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u043e \u043d\u0430 \u0442\u043e\u043c, \u0447\u0442\u043e \u0435\u0441\u043b\u0438 \u0432 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0441 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u0430\u0435\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u0435 \u0434\u043b\u044f \u0442\u043e\u0433\u043e, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u043e\u043f\u0443\u0441\u0442\u0438\u0442\u044c \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0441\u0442\u0440\u043e\u043a\u0438, \u0430 \u043d\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c \u0438\u0445 \u0441\u043d\u043e\u0432\u0430.<\/p>\n<p><strong>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0421\u043e\u0437\u0434\u0430\u0451\u0442\u0441\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 . \u042d\u0442\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0441 \u0443\u0447\u0451\u0442\u043e\u043c \u0435\u0433\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0412\u043e \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0438\u0441\u043a\u0430, \u0435\u0441\u043b\u0438 \u0441\u0438\u043c\u0432\u043e\u043b \u0432 \u0441\u0442\u0440\u043e\u043a\u0435  \u043d\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435 P, \u0448\u0430\u0431\u043b\u043e\u043d \u0441\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0441\u043e\u0432\u043f\u0430\u043b \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u0435\u043c \u044d\u0442\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435.<\/p>\n<\/li>\n<\/ol>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<p>\u041f\u0443\u0441\u0442\u044c  \u0438 .<\/p>\n<p>\u041f\u0440\u0438 \u043f\u0435\u0440\u0432\u043e\u043c \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u0435  \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0432\u0438\u0434\u0438\u0442, \u0447\u0442\u043e  \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435. \u0422\u043e\u0433\u0434\u0430 \u0448\u0430\u0431\u043b\u043e\u043d \u0441\u043c\u0435\u0449\u0430\u0435\u0442\u0441\u044f \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u043e\u0432\u043f\u0430\u043b \u0441 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<h4>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430<\/h4>\n<p>\u041f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u043c\u044b\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430\u043c\u0438. \u041a\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430\u0445 \u0434\u043b\u044f \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<p><strong>\u041f\u0440\u0438\u043d\u0446\u0438\u043f \u0440\u0430\u0431\u043e\u0442\u044b:<\/strong><\/p>\n<ol>\n<li>\n<p>\u0421\u043e\u0437\u0434\u0430\u0451\u0442\u0441\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430 . \u042d\u0442\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u044e \u043e \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f.<\/p>\n<\/li>\n<li>\n<p>\u0415\u0441\u043b\u0438 \u0447\u0430\u0441\u0442\u044c \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0441\u043e\u0432\u043f\u0430\u043b\u0430 \u0441 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438, \u043d\u043e \u0434\u0430\u043b\u0435\u0435 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u0435\u0449\u0430\u0435\u0442 \u0448\u0430\u0431\u043b\u043e\u043d \u0442\u0430\u043a, \u0447\u0442\u043e\u0431\u044b \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u044e\u0449\u0438\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0432\u044b\u0440\u043e\u0432\u043d\u044f\u043b\u0441\u044f \u0441 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u044c\u044e \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<\/li>\n<\/ol>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440:<\/strong><\/p>\n<p>\u041f\u0443\u0441\u0442\u044c \u0438 .<\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043d\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u0435  \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 \u0438  \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441\u043c\u043e\u0442\u0440\u0438\u0442 \u043d\u0430 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0438 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442, \u0447\u0442\u043e \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0439 \u0441\u0443\u0444\u0444\u0438\u043a\u0441 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0435\u0442 \u0441 \u043f\u043e\u0437\u0438\u0446\u0438\u0435\u0439 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0447\u0442\u043e \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u043c\u0435\u0441\u0442\u0438\u0442\u044c \u0448\u0430\u0431\u043b\u043e\u043d \u043d\u0430 \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0439 \u0432\u043f\u0440\u0430\u0432\u043e.<\/p>\n<h4>\u041f\u0440\u0438\u043c\u0435\u0440 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f<\/h4>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0442\u0440\u043e\u043a\u0443 T \u0438 \u0448\u0430\u0431\u043b\u043e\u043d P:<\/p>\n<ul>\n<li>\n<p><strong>\u0428\u0430\u0433 1:<\/strong> \u0412\u044b\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0441 \u043d\u0430\u0447\u0430\u043b\u043e\u043c \u0441\u0442\u0440\u043e\u043a\u0438.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 2:<\/strong> \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0441 \u043a\u043e\u043d\u0446\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 3:<\/strong> \u041f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438\u043b\u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430.<\/p>\n<\/li>\n<li>\n<p><strong>\u0428\u0430\u0433 4:<\/strong> \u0421\u043c\u0435\u0449\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0438 \u043f\u043e\u0432\u0442\u043e\u0440\u044f\u0435\u043c \u043f\u0440\u043e\u0446\u0435\u0441\u0441.<\/p>\n<\/li>\n<\/ul>\n<p>\u041f\u0440\u0438\u043c\u0435\u0440:<\/p>\n<p>\u041f\u0443\u0441\u0442\u044c  \u0438 .<\/p>\n<ol>\n<li>\n<p><strong>\u0418\u043d\u0438\u0446\u0438\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f:<\/strong><\/p>\n<ul>\n<li>\n<p>\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432: &#8216;<\/p>\n<\/li>\n<li>\n<p>\u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432: <\/p>\n<\/li>\n<\/ul>\n<\/li>\n<li>\n<p><strong>\u041f\u043e\u0438\u0441\u043a:<\/strong><\/p>\n<ul>\n<li>\n<p>\u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0441\u0442\u0440\u043e\u043a\u0443 \u0438 \u0448\u0430\u0431\u043b\u043e\u043d.<\/p>\n<\/li>\n<li>\n<p>\u041f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u043d\u0430\u0445\u043e\u0434\u0438\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u044f\u0449\u0435\u0435 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435 \u043f\u043e \u0442\u0430\u0431\u043b\u0438\u0446\u0430\u043c.<\/p>\n<\/li>\n<li>\n<p>\u0421\u043c\u0435\u0449\u0430\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u0438 \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u043c \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435.<\/p>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore \u0438\u043c\u0435\u0435\u0442 \u0441\u0440\u0435\u0434\u043d\u044e\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c  \u0434\u043b\u044f \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u0441\u043b\u0443\u0447\u0430\u0435\u0432, \u0433\u0434\u0435  \u2014 \u0434\u043b\u0438\u043d\u0430 \u0441\u0442\u0440\u043e\u043a\u0438, \u0430  \u2014 \u0434\u043b\u0438\u043d\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u042d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043e\u0447\u0435\u043d\u044c \u0445\u043e\u0440\u043e\u0448 \u043f\u0440\u0438 \u0440\u0430\u0431\u043e\u0442\u0435 \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0438 \u0441\u043b\u043e\u0436\u043d\u044b\u043c\u0438 \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c\u0438.<\/p>\n<p><strong>\u041f\u0440\u0438\u043c\u0435\u0440 \u043a\u043e\u0434\u0430:<\/strong><\/p>\n<p>\u0420\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0430\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u043c\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0443 \u043d\u0430 \u041f\u0438\u0442\u043e\u043d\u0435:<\/p>\n<pre><code class=\"python\">def boyer_moore_search(pattern, text):     def bad_character_table(pattern):         table = {}         m = len(pattern)         for i in range(m - 1):             table[pattern[i]] = i         return table      def good_suffix_table(pattern):         m = len(pattern)         table = [0] * m         last_prefix_position = m          for i in range(m - 1, -1, -1):             if is_prefix(pattern, i + 1):                 last_prefix_position = i + 1             table[m - 1 - i] = last_prefix_position - i + m - 1          for i in range(m - 1):             slen = suffix_length(pattern, i)             table[slen] = m - 1 - i + slen          return table      def is_prefix(pattern, p):         m = len(pattern)         for i in range(p, m):             if pattern[i] != pattern[i - p]:                 return False         return True      def suffix_length(pattern, p):         m = len(pattern)         length = 0         i = p         j = m - 1         while i &gt;= 0 and pattern[i] == pattern[j]:             length += 1             i -= 1             j -= 1         return length      n = len(text)     m = len(pattern)     if m == 0:         return []      bad_char_table = bad_character_table(pattern)     good_suffix_table = good_suffix_table(pattern)      s = 0     while s &lt;= n - m:         j = m - 1         while j &gt;= 0 and pattern[j] == text[s + j]:             j -= 1         if j &lt; 0:             print(f\"Pattern occurs at index {s}\")             s += good_suffix_table[0]         else:             bad_char_shift = j - bad_char_table.get(text[s + j], -1)             good_suffix_shift = good_suffix_table[j]             s += max(bad_char_shift, good_suffix_shift)  # \u043f\u0440\u0438\u043c\u0435\u0440 text = \"HERE IS A SIMPLE EXAMPLE\" pattern = \"EXAMPLE\" boyer_moore_search(pattern, text)<\/code><\/pre>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>bad_character_table(pattern)<\/code> \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u043f\u043e\u044f\u0432\u043b\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0432 \u0448\u0430\u0431\u043b\u043e\u043d\u0435, \u043a\u0440\u043e\u043c\u0435 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430.<\/p>\n<p><strong>\u0424\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>good_suffix_table(pattern)<\/code> \u0441\u043e\u0437\u0434\u0430\u0451\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u0422\u0430\u0431\u043b\u0438\u0446\u0430 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0442\u0441\u044f \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p><strong>\u0412\u0441\u043f\u043e\u043c\u043e\u0433\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <\/strong><code>is_prefix(pattern, p)<\/code> \u0438 <code>suffix_length(pattern, p)<\/code>:<\/p>\n<p><code>is_prefix<\/code> \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043e\u0442 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 <code>p<\/code> \u0434\u043e \u043a\u043e\u043d\u0446\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u043f\u0440\u0435\u0444\u0438\u043a\u0441\u043e\u043c \u0432\u0441\u0435\u0433\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0430.<\/p>\n<p><code>suffix_length<\/code> \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 \u0434\u043b\u0438\u043d\u0443 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430 \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0437\u0430\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 <code>p<\/code>.<\/p>\n<p><strong>\u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f <\/strong><code>boyer_moore_search(pattern, text)<\/code>\u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043f\u043b\u043e\u0445\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u0445\u043e\u0440\u043e\u0448\u0438\u0445 \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u043e\u0432 \u0434\u043b\u044f \u0448\u0430\u0431\u043b\u043e\u043d\u0430. \u041f\u043e\u0441\u043b\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 \u043f\u043e\u0438\u0441\u043a \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u043e\u0431\u0435 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u0434\u043b\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0433\u043e \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f\u0445. \u0410 \u0432 \u043a\u043e\u043d\u0446\u0435 \u0432\u044b\u0432\u043e\u0434\u0438\u0442 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0432\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u0439 \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435.<\/p>\n<hr\/>\n<p>\u041a\u0430\u043a \u043c\u043e\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u0438\u044c, \u044d\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u0447\u0435\u043d\u044c \u043c\u043e\u0449\u043d\u044b\u0435 \u0438 \u043a\u0430\u0436\u0434\u044b\u0435 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u0443\u043d\u0438\u043a\u0430\u043b\u044c\u043d\u044b\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u044b \u0438 \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432\u0430. <\/p>\n<p>KMP \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u043f\u0440\u0435\u0444\u0438\u043a\u0441-\u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0443\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044f \u0441\u043c\u0435\u0449\u0435\u043d\u0438\u0435\u043c \u043f\u0440\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f\u0445, \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0438\u0432\u0430\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435. <\/p>\n<p>\u0410 \u0432\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c Boyer-Moore \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442 \u0434\u0432\u0435 \u043a\u043b\u044e\u0447\u0435\u0432\u044b\u0435 \u044d\u0432\u0440\u0438\u0441\u0442\u0438\u043a\u0438: \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u043f\u043b\u043e\u0445\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0438 \u043f\u0440\u0430\u0432\u0438\u043b\u043e \u0445\u043e\u0440\u043e\u0448\u0435\u0433\u043e \u0441\u0443\u0444\u0444\u0438\u043a\u0441\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u044e\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u043e \u0443\u0441\u043a\u043e\u0440\u0438\u0442\u044c \u043f\u0440\u043e\u0446\u0435\u0441\u0441 \u043f\u043e\u0438\u0441\u043a\u0430 \u0437\u0430 \u0441\u0447\u0451\u0442 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0430 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<p>\u0412\u044b\u0431\u043e\u0440 \u043c\u0435\u0436\u0434\u0443 KMP \u0438 Boyer-Moore \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u043e\u0433\u043e \u0441\u043b\u0443\u0447\u0430\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u0438 \u0442\u0440\u0435\u0431\u043e\u0432\u0430\u043d\u0438\u0439 \u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438. <\/p>\n<blockquote>\n<p>\u0420\u0430\u0437\u0432\u0438\u0432\u0430\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043c\u044b\u0448\u043b\u0435\u043d\u0438\u0435 \u0438 \u0443\u0447\u0438\u0442\u044c\u0441\u044f \u0443\u0432\u0435\u043b\u0438\u0447\u0438\u0432\u0430\u0442\u044c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c \u043c\u043e\u0436\u043d\u043e <a href=\"https:\/\/otus.pw\/NYeK\/\">\u043d\u0430 \u043e\u043d\u043b\u0430\u0439\u043d-\u043a\u0443\u0440\u0441\u0435 \u00ab\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445\u00bb<\/a> \u0432 \u041e\u0442\u0443\u0441.<\/p>\n<\/blockquote>\n<\/div>\n<\/div>\n<\/div>\n<p><!----><!----><\/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\/articles\/828572\/\"><\/a><\/br><\/p>\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-427321","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/427321","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=427321"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/427321\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=427321"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=427321"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=427321"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}