{"id":459590,"date":"2025-05-14T09:14:08","date_gmt":"2025-05-14T09:14:08","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=459590"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=459590","title":{"rendered":"<span>\u0411\u044b\u0441\u0442\u0440\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c fulltext-\u043f\u043e\u0438\u0441\u043a\u0430 \u0431\u0435\u0437 \u0442\u043e\u043a\u0435\u043d\u0438\u0437\u0430\u0446\u0438\u0438<\/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<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ed0\/f94\/281\/ed0f94281ff0d5f354999f58ea0c5ab4.jpg\" width=\"780\" height=\"440\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/ed0\/f94\/281\/ed0f94281ff0d5f354999f58ea0c5ab4.jpg 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ed0\/f94\/281\/ed0f94281ff0d5f354999f58ea0c5ab4.jpg 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u041c\u0435\u043d\u044f \u0437\u043e\u0432\u0443\u0442 \u0414\u043c\u0438\u0442\u0440\u0438\u0439 \u041e\u043b\u044c\u0448\u0430\u043d\u0441\u043a\u0438\u0439, \u044f \u0432\u0435\u0434\u0443\u0449\u0438\u0439 \u0438\u043d\u0436\u0435\u043d\u0435\u0440 \u0422-\u0411\u0430\u043d\u043a\u0430. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u043d\u043e\u0432\u043e\u043c (\u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e) \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u0435\u043a\u0441\u0442\u0430 \u043f\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0443. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u043f\u0440\u043e\u0435\u043a\u0442\u0430 <a href=\"https:\/\/sage-observability.tech\/\">Sage<\/a> \u2014 observability-\u043f\u043b\u0430\u0442\u0444\u043e\u0440\u043c\u044b \u043e\u0442 \u0422-\u0411\u0430\u043d\u043a\u0430, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043d\u043e\u0432\u044b\u0439 \u0431\u044d\u043a\u044d\u043d\u0434 \u0434\u043b\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043b\u043e\u0433\u043e\u0432, <a href=\"https:\/\/ecode.ozon.tech\/archive\/E%E2%80%93Code%202024\/talks\/d19c95082dc1419685ff9ad9da240a23\/?__rr=1&amp;abt_att=1\">SageDB.<\/a>\u00a0<\/p>\n<h2>\u041a\u0430\u043a\u0430\u044f \u0431\u044b\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430<\/h2>\n<p>\u0418\u043c\u0435\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0437\u0430\u043f\u0440\u043e\u0441 hello *orld, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043d\u0430\u0439\u0442\u0438 \u0441\u0442\u0440\u043e\u043a\u0438, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u043a\u0430\u043a hello world, \u0442\u0430\u043a \u0438 hello, wonderful world, \u2014 \u0442\u043e \u0435\u0441\u0442\u044c \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0430 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442 \u043b\u044e\u0431\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u043c\u044b \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u0435\u043c \u0437\u043d\u0430\u043a\u0438 \u043f\u0440\u0435\u043f\u0438\u043d\u0430\u043d\u0438\u044f.\u00a0<\/p>\n<p>\u0414\u043b\u044f \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0441 \u0442\u043e\u043a\u0435\u043d\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u044d\u0442\u043e \u0432\u044b\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b: \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u0432\u0441\u0435 \u0442\u043e\u043a\u0435\u043d\u044b, \u043e\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043d\u0430 orld, \u0438 \u0438\u043c\u0435\u0442\u044c \u0432 \u0432\u0438\u0434\u0443 \u043f\u0440\u043e\u043f\u0443\u0441\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0442\u043e\u043a\u0435\u043d\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 hello \u0438 \u043a\u043e\u043d\u0446\u0435\u0432\u044b\u043c \u0442\u043e\u043a\u0435\u043d\u043e\u043c. \u0411\u043e\u043b\u044c\u0448\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u0435\u043a \u2014 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c.\u00a0<\/p>\n<p>\u0412 SageDB \u043c\u044b \u0441\u043e\u0437\u043d\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0442\u0445\u043e\u0434\u0438\u043c \u043e\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u044b\u0445 inverted index \u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c brute-force-\u0442\u0430\u043a\u0442\u0438\u043a\u0443 \u2014 \u0438\u0449\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u043f\u043e \u0432\u0441\u0435\u043c \u043e\u0442\u0444\u0438\u043b\u044c\u0442\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0441\u0442\u0440\u043e\u043a\u0430\u043c.<\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u0435\u043a\u0441\u0442\u0430 \u043f\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c, \u043f\u0435\u0440\u0432\u043e\u0435, \u0447\u0442\u043e \u043f\u0440\u0438\u0448\u043b\u043e \u0432 \u0433\u043e\u043b\u043e\u0432\u0443, \u2014 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0428\u0430\u0431\u043b\u043e\u043d hello <em>orld \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u0430\u043a \\bhello\\s+.<\/em>orld\\b, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0441\u043b\u043e\u0432\u0430 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043f\u0440\u043e\u0431\u0435\u043b\u0430\u043c\u0438.\u00a0<\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044f \u0435\u0449\u0435 \u0438 \u0430\u0432\u0442\u043e\u0440 <a href=\"https:\/\/dlang.org\/phobos\/std_regex.html\">std.regex-\u043c\u043e\u0434\u0443\u043b\u044f \u044f\u0437\u044b\u043a\u0430 D<\/a>, \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u043c\u0435\u043d\u044f \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0434\u0438\u0432\u0438\u043b\u0438: \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043d\u0430\u043a\u043b\u0430\u0434\u043d\u044b\u0435 \u0440\u0430\u0441\u0445\u043e\u0434\u044b \u043d\u0430 \u0437\u0430\u043f\u0443\u0441\u043a \u0434\u0432\u0438\u0436\u043a\u0430 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a\u0430\u0445.\u00a0<\/p>\n<p>\u0414\u0430\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 <a href=\"https:\/\/github.com\/intel\/hyperscan\">Hyperscan<\/a> \u043d\u0435 \u0434\u0430\u043b\u043e \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u043b\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u0446\u0438\u0438 \u0441 JVM, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430\u0448 \u0434\u0432\u0438\u0436\u043e\u043a \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u043d\u0430 Java. \u041f\u043b\u0430\u0442\u0430 \u0437\u0430 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0432\u044b\u0441\u043e\u043a\u0430 \u0438 \u043c\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0438 \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0442\u0430\u043c, \u0433\u0434\u0435 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e.\u00a0<\/p>\n<p>\u0422\u0430\u043a \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c \u0438\u0434\u0435\u044f \u0432\u0437\u044f\u0442\u044c \u0437\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c Shift-Or \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u043d\u0430\u0448\u0438\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c. \u042d\u0442\u043e \u0431\u044b\u043b \u043f\u0443\u0442\u044c \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432, \u0438 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u043c\u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u0438 \u0432\u043e\u0432\u0441\u0435 \u0443\u043b\u043e\u0436\u0438\u0442\u044c \u0432\u0441\u044e \u043b\u043e\u0433\u0438\u043a\u0443 \u043d\u0430\u0448\u0438\u0445 \u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f \u043d\u0430\u0437\u044b\u0432\u0430\u043b <abbr class=\"habraabbr\" title=\"NFA - Nondeterministic Finite-state Automaton\" data-title=\"&lt;p&gt;NFA - Nondeterministic Finite-state Automaton&lt;\/p&gt;\" data-abbr=\"BitNFA.\">BitNFA.<\/abbr> \u041f\u043e\u043a\u0430\u0436\u0443 \u043d\u0430\u0448 \u043f\u0443\u0442\u044c \u043f\u043e \u0448\u0430\u0433\u0430\u043c \u0438 \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443, \u043a\u0430\u043a \u0438\u0437 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438\u0434\u0435\u0438 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/p>\n<h2>\u041d\u0430\u0447\u0430\u043b\u043e \u2014 Shift-Or<\/h2>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c\u0441\u044f \u0441 \u0441\u0430\u043c\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c Shift-Or. \u0412 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u043f\u043e \u044d\u0442\u043e\u0439 \u0442\u0435\u043c\u0435, \u043a\u0430\u043a \u043c\u043d\u0435 \u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0443\u0432\u043b\u0435\u043a\u0430\u044e\u0442\u0441\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c\u0438, \u0443\u043f\u0443\u0441\u043a\u0430\u044f \u0433\u043b\u0430\u0432\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e NFA. \u0422\u0430\u043a \u0447\u0442\u043e \u043b\u0443\u0447\u0448\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u2014 \u044d\u0442\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 NFA, \u0430 \u0437\u0430\u0442\u0435\u043c \u0443\u0436\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0431\u0438\u0442\u0430\u043c.\u00a0<\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 ababc \u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0434\u043b\u044f \u0435\u0435 \u043f\u043e\u0438\u0441\u043a\u0430. \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043e\u0434\u043d\u043e \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u043e, \u2014 \u0442\u0430\u043a \u043c\u044b \u00ab\u043f\u0440\u0438\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u043c\u00bb \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u043a \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0442\u0435\u043a\u0441\u0442\u0435. \u0414\u0430\u043b\u0435\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u043d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438, \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u044b \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u043e\u0436\u0438\u0434\u0430\u0435\u043c \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435. \u041d\u0430\u043a\u043e\u043d\u0435\u0446, \u0435\u0441\u0442\u044c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u2014 \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0441\u0442\u0430\u043b\u043e \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u043e\u0441\u043b\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443.<\/p>\n<p>\u0412 \u0447\u0435\u043c \u0436\u0435 \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430? \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u043e\u0442\u0432\u0435\u0442 \u2014 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0430\u043a\u0442\u0438\u0432\u043d\u044b \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0422\u0430\u043a\u0430\u044f \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 abababc. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u043c\u044b \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b\u0438 ab, \u043c\u044b \u0441\u043d\u043e\u0432\u0430 \u0432\u0438\u0434\u0438\u043c a \u2014 \u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043d\u0435 \u0437\u043d\u0430\u0435\u043c, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043d\u0430\u0439\u0434\u0435\u043d\u0430 \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 a \u0438\u043b\u0438 \u0441\u043e \u0432\u0442\u043e\u0440\u043e\u0433\u043e. \u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0442\u043e\u0436\u0435 \u044d\u0442\u043e\u0433\u043e \u00ab\u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u00bb \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0434\u0432\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u043e\u0442\u0440\u0430\u0436\u0430\u044e\u0449\u0438\u0445 \u044d\u0442\u043e\u0442 \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0437\u043c.\u00a0<\/p>\n<p>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u0440\u043e\u0441\u0442: \u043c\u044b \u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432. \u0415\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434, \u043c\u044b \u043f\u0435\u0440\u0435\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0432\u043f\u0435\u0440\u0435\u0434. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438\u0441\u0447\u0435\u0437\u0430\u0435\u0442.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/4a3\/e88\/36e\/4a3e8836ee863f388de577319f057769.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430\" width=\"881\" height=\"81\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/4a3\/e88\/36e\/4a3e8836ee863f388de577319f057769.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/4a3\/e88\/36e\/4a3e8836ee863f388de577319f057769.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430<\/figcaption><\/div>\n<\/figure>\n<p>\u041f\u043e\u0438\u0441\u043a \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0438\u0437\u044f\u0449\u0435\u043d, \u043d\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0433\u0434\u0435-\u0442\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e: \u0437\u0430 O(mn), \u0433\u0434\u0435 m \u2014 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0432 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0435, \u0430 n \u2014 \u0440\u0430\u0437\u043c\u0435\u0440 \u0442\u0435\u043a\u0441\u0442\u0430.\u00a0<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u0438\u043a\u0438 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f NFA, \u043d\u043e \u043f\u043e-\u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u043c\u0443 \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u2014 \u044d\u0442\u043e Shift-Or. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0438 \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0447\u0438\u0441\u043b\u043e \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f. \u0422\u0435\u043f\u0435\u0440\u044c \u0435\u0441\u043b\u0438 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u043d\u044c\u0448\u0435 64 (\u0434\u043b\u044f 64-\u0431\u0438\u0442\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, 32 \u0434\u043b\u044f 32-\u0431\u0438\u0442\u043d\u044b\u0445), \u0442\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043b\u044e\u0431\u0443\u044e \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044e \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043a\u0430\u043a \u043e\u0434\u043d\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e. \u041a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434\u0430\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0431\u0438\u0442: 0 \u0431\u0443\u0434\u0435\u0442 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0430 1 \u2014 \u043d\u0435\u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c. \u041d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0443\u0436\u0435 \u043f\u0440\u043e\u0448\u0435\u043b \u0447\u0435\u0440\u0435\u0437 abab \u0438 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438 \u043e\u0441\u0442\u0430\u043b\u0438\u0441\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f 1 \u0438 3.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/602\/7a2\/d5b\/6027a2d5ba9f520cd707889a03ed2b29.png\" alt=\"\u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0431\u0438\u0442\u0430\u043c \u0432 \u0441\u043b\u043e\u0432\u0435\" title=\"\u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0431\u0438\u0442\u0430\u043c \u0432 \u0441\u043b\u043e\u0432\u0435\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/602\/7a2\/d5b\/6027a2d5ba9f520cd707889a03ed2b29.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/602\/7a2\/d5b\/6027a2d5ba9f520cd707889a03ed2b29.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0431\u0438\u0442\u0430\u043c \u0432 \u0441\u043b\u043e\u0432\u0435<\/figcaption><\/div>\n<\/figure>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u0442\u0430\u043a\u043e\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0448\u0430\u0433 \u2014 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438. \u041b\u0435\u0433\u043a\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0439 \u0441\u0434\u0432\u0438\u0433 \u043f\u0435\u0440\u0435\u0432\u0435\u0434\u0435\u0442 \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0440\u0430\u0437\u043e\u043c \u0432\u043f\u0435\u0440\u0435\u0434.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0e2\/618\/285\/0e2618285f1c8e55de5b88a7912b55de.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0441\u0434\u0432\u0438\u0433\u0443 \u0432\u0441\u0435\u0445 \u0431\u0438\u0442 \u043d\u0430 1\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0441\u0434\u0432\u0438\u0433\u0443 \u0432\u0441\u0435\u0445 \u0431\u0438\u0442 \u043d\u0430 1\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/0e2\/618\/285\/0e2618285f1c8e55de5b88a7912b55de.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0e2\/618\/285\/0e2618285f1c8e55de5b88a7912b55de.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0441\u0434\u0432\u0438\u0433\u0443 \u0432\u0441\u0435\u0445 \u0431\u0438\u0442 \u043d\u0430 1<\/figcaption><\/div>\n<\/figure>\n<p>\u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u0444\u0438\u043b\u044c\u0442\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u043e\u0441\u0442\u0430\u0442\u044c\u0441\u044f \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418\u041b\u0418 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043c\u0430\u0441\u043a\u043e\u0439 \u2014 \u043e\u043d\u0430, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0441\u0432\u043e\u044f. \u0412\u0430\u0436\u043d\u043e \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439, \u0442\u0430\u043a \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u043c\u0430\u0441\u043e\u043a \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u0434\u043b\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430.<\/p>\n<p>\u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 a \u0438 b \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430, \u0438\u043c \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u0431\u0438\u0442\u0430 \u0432 \u043c\u0430\u0441\u043a\u0435, \u0442\u0430\u043a \u043c\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043c \u043d\u0443\u043b\u0438 \u043f\u0440\u0438 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u043c\u0430\u0441\u043a\u0438 \u0447\u0435\u0440\u0435\u0437 \u0418\u041b\u0418.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ae8\/ead\/a77\/ae8eada77b03ba259178e3952488a73d.png\" alt=\"\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u2014 \u00ab\u0430\u00bb \" title=\"\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u2014 \u00ab\u0430\u00bb \" width=\"922\" height=\"291\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/ae8\/ead\/a77\/ae8eada77b03ba259178e3952488a73d.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/ae8\/ead\/a77\/ae8eada77b03ba259178e3952488a73d.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u2014 \u00ab\u0430\u00bb <\/figcaption><\/div>\n<\/figure>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bdd\/1b9\/34d\/bdd1b934dad0a895dc61679bfefa4ffb.png\" alt=\"\u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e\u0441\u043b\u0435 \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u00ab\u0430\u00bb\u00a0\" title=\"\u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e\u0441\u043b\u0435 \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u00ab\u0430\u00bb\u00a0\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/bdd\/1b9\/34d\/bdd1b934dad0a895dc61679bfefa4ffb.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bdd\/1b9\/34d\/bdd1b934dad0a895dc61679bfefa4ffb.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e\u0441\u043b\u0435 \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u00ab\u0430\u00bb\u00a0<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0430\u0434\u0438\u044e: \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0443 \u043d\u0430\u0441 \u2014 \u0434\u0432\u0430 \u043d\u0443\u043b\u044f \u0432 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u0445 1 \u0438 3 \u043f\u043e\u0441\u043b\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 b.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/8a5\/266\/8c9\/8a52668c97bbf591365a86333dff3932.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0442\u0440\u0435\u0442\u044c\u0435\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 b\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0442\u0440\u0435\u0442\u044c\u0435\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 b\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/8a5\/266\/8c9\/8a52668c97bbf591365a86333dff3932.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/8a5\/266\/8c9\/8a52668c97bbf591365a86333dff3932.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0442\u0440\u0435\u0442\u044c\u0435\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 b<\/figcaption><\/div>\n<\/figure>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0434\u0432\u0438\u0433 \u0431\u0438\u0442\u043e\u0432, \u0442\u0435\u043f\u0435\u0440\u044c \u0443 \u043d\u0430\u0441 \u0430\u043a\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d52\/c9b\/ce7\/d52c9bce7ae4ae4fcfd49c2d12dd7b57.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/d52\/c9b\/ce7\/d52c9bce7ae4ae4fcfd49c2d12dd7b57.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/d52\/c9b\/ce7\/d52c9bce7ae4ae4fcfd49c2d12dd7b57.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430<\/figcaption><\/div>\n<\/figure>\n<p>\u0424\u0438\u043b\u044c\u0442\u0440\u0430\u0446\u0438\u044f \u0447\u0435\u0440\u0435\u0437 \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 c.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/81c\/e9b\/95c\/81ce9b95ca3aa0f2960d868d59614c97.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430\" width=\"922\" height=\"291\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/81c\/e9b\/95c\/81ce9b95ca3aa0f2960d868d59614c97.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/81c\/e9b\/95c\/81ce9b95ca3aa0f2960d868d59614c97.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430<\/figcaption><\/div>\n<\/figure>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/055\/81c\/cf0\/05581ccf03eb6731943639e693b0da05.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0441\u043a\u0438\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0441\u043a\u0438\" width=\"881\" height=\"206\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/055\/81c\/cf0\/05581ccf03eb6731943639e693b0da05.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/055\/81c\/cf0\/05581ccf03eb6731943639e693b0da05.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0441\u043a\u0438<\/figcaption><\/div>\n<\/figure>\n<p>\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0431\u0438\u0442\u0430, \u043f\u0440\u0438 \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u0438 \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043f\u043e\u0438\u0441\u043a \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f, \u0442\u0430\u043a\u043e\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0435 \u0418 \u2014 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f 0 \u043f\u0440\u0438 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0441\u043a\u0438. \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0431\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0435 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442, \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043b\u043e\u0432\u043e\u043c.<\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/163\/5d5\/868\/1635d5868611dae6bcaebb0849bbea0e.png\" alt=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0432 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0434\u0438\u0438\" title=\"\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0432 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0434\u0438\u0438\" width=\"922\" height=\"291\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/163\/5d5\/868\/1635d5868611dae6bcaebb0849bbea0e.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/163\/5d5\/868\/1635d5868611dae6bcaebb0849bbea0e.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/p>\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0432 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0434\u0438\u0438<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432 \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434\u0435 \u0421\u0438-\u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430 \u2014 \u0435\u0433\u043e \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0430 \u0421\/\u0421++\/Java\/C#\/Rust. \u0413\u043b\u0430\u0432\u043d\u043e\u0435, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u0414\u0430\u043b\u0435\u0435 \u0441 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439 \u0438 \u043c\u0430\u0441\u043a\u043e\u0439 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u044f \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u0438 \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u0443\u044e \u043d\u0430\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443.\u00a0<\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0446\u0438\u043a\u043b \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u044f\u043c\u043e\u043b\u0438\u043d\u0435\u0435\u043d \u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0447\u0442\u0435\u043d\u0438\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0434\u0432\u0438\u0433\u0430 \u0432\u043b\u0435\u0432\u043e, \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418\u041b\u0418 \u0438 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418. \u0422\u0430\u043a\u0438\u0435 \u043f\u043b\u043e\u0442\u043d\u044b\u0435 \u0446\u0438\u043a\u043b\u044b \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043d\u0430 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430\u0445, \u0438 \u043f\u0440\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043c\u043e\u0442\u0430\u0442\u044c (unroll), \u0447\u0442\u043e, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0438 \u0441\u0434\u0435\u043b\u0430\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 JIT).<\/p>\n<pre><code class=\"java\">long[256] table; long finish;  prepare(string substring) {     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (int i=0; i&lt;substring.length; i++) {         table[substring[i]] &amp;= ~(1L&lt;&lt;i); \/\/\u043d\u043e\u043b\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i     }     finish = 1&lt;&lt;(substring.length-1); } search(string input) {     long state = -1L;     for(int i=0; i&lt;input.length;i++) {         state &lt;&lt;= 1;         char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;     }     return false; }<\/code><\/pre>\n<h2>\u0420\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0431 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430: \u043e\u043d \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0432 \u043b\u043e\u0433\u0438\u043a\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u044b \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043f\u0440\u044f\u043c\u043e \u043a\u0430\u043a \u0432 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u0445. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e. \u041c\u044b \u043b\u0435\u0433\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u044b \u0441 \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u043c \u2018\\s\u2019 \u2014 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043f\u043e \u043b\u044e\u0431\u043e\u043c\u0443 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0439 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u0435\u043c \u0443\u0447\u0435\u0441\u0442\u044c \u0435\u0449\u0435 \u0438 \u0437\u043d\u0430\u043a\u0438 \u043f\u0440\u0435\u043f\u0438\u043d\u0430\u043d\u0438\u044f) \u0438 \u0434\u0430\u0436\u0435 \u2018.\u2019 \u2014 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0443 \u043f\u043e \u043b\u044e\u0431\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443. <\/p>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bef\/81e\/706\/bef81e7064af72b76baf98a80d86ab0d.png\" width=\"721\" height=\"141\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/bef\/81e\/706\/bef81e7064af72b76baf98a80d86ab0d.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/bef\/81e\/706\/bef81e7064af72b76baf98a80d86ab0d.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u0421 \u043a\u043b\u0430\u0441\u0441\u0430\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u0442\u0435\u043f\u0435\u0440\u044c \u0447\u0442\u043e \u0442\u0430\u043c \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0430\u043c\u0438 \u0438\u0437 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0439? \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0432\u043d\u0435\u0434\u0440\u0438\u0442\u044c \u0432 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u043f\u043e\u043d\u044f\u0442\u0438\u0435 \u2018\\s+\u2019 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0412\u044b\u0434\u0435\u043b\u0438\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0431\u0438\u0442 \u043f\u043e\u0434 \\s. \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0441\u0434\u0432\u0438\u0433\u0430 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u2018\\s\u2019 \u0441\u043d\u043e\u0432\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u0441\u0435 \u0432 \u0431\u0438\u0442\u0430\u0445, \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u0438\u0442\u043e\u0432\u0443\u044e \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0441 \u043f\u043b\u044e\u0441\u043e\u043c.\u00a0<\/p>\n<p>\u041d\u0430\u043b\u043e\u0436\u0438\u043c \u043c\u0430\u0441\u043a\u0443 \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0441\u043b\u043e\u0432\u043e \u0447\u0435\u0440\u0435\u0437 \u0418\u041b\u0418, \u0441\u043e\u0431\u0438\u0440\u0430\u044f \u043d\u0443\u043b\u0438 \u0432 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u0445 \u043d\u0430 \u044d\u0442\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445, \u0441\u0434\u0432\u0438\u043d\u0435\u043c \u043d\u0430\u0437\u0430\u0434 \u0438 \u043e\u043f\u044f\u0442\u044c \u043d\u0430\u043b\u043e\u0436\u0438\u043c \u0443\u0436\u0435 \u0447\u0435\u0440\u0435\u0437 \u0418, \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0430\u0437\u0430\u0434. \u0422\u0430\u043a \u043c\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0446\u0438\u043a\u043b\u0438\u0447\u043d\u043e\u0441\u0442\u044c \u0432 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041c\u044b \u043d\u0435 \u0442\u0435\u0440\u044f\u0435\u043c \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432 \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430, \u043e\u0434\u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043e\u0431\u0441\u043b\u0443\u0436\u0438\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c.<\/p>\n<pre><code class=\"java\">long[256] table; long finish; long plus_mask;  prepare(string pattern) {     plus_mask = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (int i=0; i&lt;pattern.length; i++) {         char c = pattern[i];         long mask = (1L&lt;&lt;i); \/\/\u043d\u043e\u043b\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i         if (isPaddingSymbol(c)) { \/\/ \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b             for (p in PADDING_SYMBOLS) {                 table[p] &amp;= ~mask;             }             \/\/ \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c 0 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430             plus_mask &amp;= ~mask;           } else {             table[c] &amp;= ~mask;         }     }     finish = 1&lt;&lt;(pattern.length-1); } search(string input) {     long state = -1L;     for(int i=0; i&lt;input.length;i++) {         state &lt;&lt;= 1;         \/\/ \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043d\u0430 1 \u043d\u0430\u0437\u0430\u0434         state &amp;= (state | (plus_mask &lt;&lt; 1)) &gt;&gt; 1;          char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;     }     return false; }<\/code><\/pre>\n<figure class=\"full-width\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0e8\/a4d\/c2d\/0e8a4dc2da3e0e7061d68bb5f99e4da1.png\" width=\"721\" height=\"141\" sizes=\"auto, (max-width: 780px) 100vw, 50vw\" srcset=\"https:\/\/habrastorage.org\/r\/w780\/getpro\/habr\/upload_files\/0e8\/a4d\/c2d\/0e8a4dc2da3e0e7061d68bb5f99e4da1.png 780w,&#10;       https:\/\/habrastorage.org\/r\/w1560\/getpro\/habr\/upload_files\/0e8\/a4d\/c2d\/0e8a4dc2da3e0e7061d68bb5f99e4da1.png 781w\" loading=\"lazy\" decode=\"async\"\/><\/figure>\n<p>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c, \u0447\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u043e\u0439, \u0442\u0430\u043a \u043a\u0430\u043a \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u0440\u0438\u0432\u044b\u0447\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435. \u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0438 \u043b\u0438\u0448\u044c \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0435\u0440\u0435\u0434\u0432\u0438\u043d\u0443\u0442\u044c \u0432\u043f\u0435\u0440\u0435\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0447\u0442\u043e\u0431\u044b \u0443\u0447\u0435\u0441\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0443\u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u044f. \u0422\u0430\u043a \u0447\u0442\u043e \u0434\u043b\u044f . \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0442\u043e\u0442 \u0436\u0435 \u043f\u043e\u0434\u0445\u043e\u0434, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u0430\u0441\u043a\u0430 \u0434\u043b\u044f \u043f\u043b\u044e\u0441\u0430 \u0431\u0443\u0434\u0435\u0442 \u0430\u043a\u0442\u0438\u0432\u043d\u0430 \u0438 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f.\u00a0<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u0442\u044c .+ \u0432 .*, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0443\u0447\u0435\u0441\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u041d\u0430 \u044f\u0437\u044b\u043a\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u044d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u044d\u043f\u0441\u0438\u043b\u043e\u043d-\u043f\u0435\u0440\u0435\u0445\u043e\u0434\u00bb, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0434\u0430\u0436\u0435 \u0431\u0435\u0437 \u0441\u0438\u043c\u0432\u043e\u043b\u0430. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u0441\u0435 \u0443 \u043d\u0430\u0441 \u0432 \u0431\u0438\u0442\u043e\u0432\u043e\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435, \u043e\u043f\u044f\u0442\u044c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043c\u0430\u0441\u043a\u0430, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u044d\u0442\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0414\u0430\u043b\u044c\u0448\u0435 \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u043e: \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0432 \u043c\u0430\u0441\u043a\u0443, \u0441\u0434\u0432\u0438\u043d\u0435\u043c \u0432\u043f\u0435\u0440\u0435\u0434 \u0438 \u0441\u043d\u043e\u0432\u0430 \u043d\u0430\u043b\u043e\u0436\u0438\u043c \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0441\u043b\u043e\u0432\u043e.<\/p>\n<pre><code class=\"java\">long[256] table; long finish; long plus_mask; long star_mask;  prepare(string pattern) {     plus_mask = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     star_mask = -1L; \/\/     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (int i=0; i&lt;pattern.length; i++) {         char c = pattern[i];         long mask = (1L&lt;&lt;i); \/\/\u043d\u043e\u043b\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i         if (c == '*') {             for (int j=0; j&lt;256; j++) {                 c[j] &amp;= ~mask;             }             \/\/start_mask \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u0430 \u0441\u0434\u0432\u0438\u0433 \u0432\u043f\u0435\u0440\u0435\u0434             \/\/star_mask \u0437\u0430 \u0441\u0434\u0432\u0438\u0433 \u043d\u0430\u0437\u0430\u0434 \u0442\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u044f             plus_mask &amp;= ~mask;             star_mask &amp;= ~mask;         }         else if (isPaddingSymbol(c)) { \/\/ \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b             for (p in PADDING_SYMBOLS) {                 table[p] &amp;= ~mask;             }             \/\/ \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c 0 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430             plus_mask &amp;= ~mask;           } else {             table[c] &amp;= ~mask;         }     }     finish = 1&lt;&lt;(pattern.length-1); } search(string input) {     long state = -1L;     for(int i=0; i&lt;input.length;i++) {         state &lt;&lt;= 1;         \/\/ \u043f\u0440\u043e\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0432\u043f\u0435\u0440\u0435\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u043e\u0439         long state1 = (state | star) &lt;&lt; 1;   \/\/ \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043d\u0430 1 \u043d\u0430\u0437\u0430\u0434         long state2 = (state | (plus_mask &lt;&lt; 1)) &gt;&gt; 1;          state = state &amp; state1 &amp; state2;         char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;     }     return false; }<\/code><\/pre>\n<p>\u041c\u044b \u0440\u0435\u0430\u043b\u0438\u0437\u043e\u0432\u0430\u043b\u0438 \u043b\u0438\u0448\u044c \u0447\u0442\u043e-\u0442\u043e \u0432\u0440\u043e\u0434\u0435<code> \\s+hello\\s+.*orld\\s+<\/code> \u0432 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441 \u0438\u0441\u043a\u043e\u043c\u044b\u043c <code>\\bhello\\s+.*orld\\b.<\/code> \u0417\u0434\u0435\u0441\u044c \u0432\u0441\u0435 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u043f\u0440\u043e\u0441\u0442\u043e: \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430 \u043c\u044b \u0441\u0434\u0435\u043b\u0430\u0435\u043c \u0434\u0432\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438 \u0441\u0440\u0430\u0437\u0443 \u2014 \u0438 \u2018\\s+\u2019, \u0438 \u2018h\u2019. \u041a\u043e\u043d\u0446\u043e\u0432\u043a\u0430 \u0442\u0430\u043a\u0436\u0435 \u0440\u0435\u0448\u0430\u0435\u0442\u0441\u044f \u0434\u043e\u043f\u043e\u043b\u043d\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0439 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u043e\u0439 \u043f\u043e\u0441\u043b\u0435 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0434\u0432\u0438\u0433\u0430 \u0432\u043b\u0435\u0432\u043e.<\/p>\n<pre><code class=\"java\">long[256] table; long finish; long plus_mask; long star_mask;  prepare(string pattern) {     plus_mask = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     star_mask = -1L; \/\/     long mask = 1     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (c in PADDING_SYMBOLS) {         table[c] = ~mask;     }     plus_mask &amp;= ~mask;     for (int i=0; i&lt;pattern.length; i++) {         char c = pattern[i];         mask &lt;&lt;= 1;         if (c == '*') {             for (int j=0; j&lt;256; j++) {                 c[j] &amp;= ~mask;             }             \/\/start_mask \u043e\u0442\u0432\u0435\u0447\u0430\u0435\u0442 \u0442\u043e\u043b\u044c\u043a\u043e \u0437\u0430 \u0441\u0434\u0432\u0438\u0433 \u0432\u043f\u0435\u0440\u0435\u0434             \/\/star_mask \u0437\u0430 \u0441\u0434\u0432\u0438\u0433 \u043d\u0430\u0437\u0430\u0434 \u0442\u0435 \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u044f             plus_mask &amp;= ~mask;             star_mask &amp;= ~mask;         }         else if (isPaddingSymbol(c)) { \/\/ \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b             for (p in PADDING_SYMBOLS) {                 table[p] &amp;= ~mask;             }             \/\/ \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c 0 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430             plus_mask &amp;= ~mask;           } else {             table[c] &amp;= ~mask;         }         if (pattern[pattern.length-1] != '*') {             mask = mask shl 1;             for (p in PADDING_SYMBOLS) {                 table[p] &amp;= ~mask;             }             \/\/ \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c 0 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430             plus_mask &amp;= ~mask;           }     }     finish = mask; } search(string input) {     long state = -4L; \/\/ \u043f\u0435\u0440\u0432\u044b\u0435 \u0434\u0432\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0430\u043a\u0442\u0438\u0432\u043d\u044b     for(int i=0; i&lt;input.length;i++) {   \/\/ \u043f\u0440\u043e\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0432\u043f\u0435\u0440\u0435\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u043e\u0439         long state1 = (state | star) &lt;&lt; 1;   \/\/ \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043d\u0430 1 \u043d\u0430\u0437\u0430\u0434         long state2 = (state | (plus_mask &lt;&lt; 1)) &gt;&gt; 1;          state = state &amp; state1 &amp; state2;          char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;         state &lt;&lt;= 1;     }     return (state &amp; finish) == 0; }<\/code><\/pre>\n<h2>\u041f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c<\/h2>\n<p>\u0421\u0442\u043e\u0438\u043b\u043e \u043b\u0438 \u0431\u043e\u0440\u043e\u0442\u044c\u0441\u044f? \u0421\u043e \u0432\u0441\u0435\u043c\u0438 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u044f\u043c\u0438 \u043c\u044b \u0434\u0435\u043b\u0430\u0435\u043c \u043f\u0440\u0438\u043b\u0438\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c \u0446\u0438\u043a\u043b\u0435. \u0417\u0434\u0435\u0441\u044c \u0438\u043c\u0435\u0435\u0442 \u0441\u043c\u044b\u0441\u043b \u0437\u0430\u043d\u044f\u0442\u044c\u0441\u044f \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430\u043c\u0438.\u00a0<\/p>\n<p>\u0413\u043b\u0430\u0432\u043d\u043e\u0435, \u0447\u0442\u043e \u043c\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043b\u0438, \u2014 \u044d\u0442\u043e \u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0412\u043d\u0435 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u0435\u043a \u0438\u043b\u0438 \u0434\u043b\u0438\u043d\u044b \u0448\u0430\u0431\u043b\u043e\u043d\u0430 \u043f\u043e\u0438\u0441\u043a \u0437\u0430\u043d\u0438\u043c\u0430\u0435\u0442 \u0444\u0438\u043a\u0441\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 O(n).\u00a0<\/p>\n<p>\u0414\u043b\u044f \u0431\u0435\u043d\u0447\u043c\u0430\u0440\u043a\u0430 \u0432\u044b\u0431\u0435\u0440\u0435\u043c \u0442\u0440\u0438 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430 \u0438 \u0442\u0440\u0438 \u0441\u0442\u0440\u043e\u043a\u0438, \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u0441\u044f \u043c\u0430\u0442\u0440\u0438\u0446\u0430 \u043d\u0430 \u0434\u0435\u0432\u044f\u0442\u044c \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u0439 \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430. \u0421\u0442\u0440\u043e\u043a\u0438 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0441\u043e\u0431\u043e\u0439 \u0442\u0438\u043f\u043e\u0432\u044b\u0435 \u0441\u043e\u043e\u0431\u0449\u0435\u043d\u0438\u044f \u0438\u0437 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0445 \u043b\u043e\u0433\u043e\u0432, \u043f\u0440\u0438 \u044d\u0442\u043e\u043c third \u043e\u0442\u043b\u0438\u0447\u0430\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u2014 \u043e\u043a\u043e\u043b\u043e \u043a\u0438\u043b\u043e\u0431\u0430\u0439\u0442\u0430. \u0412 \u043a\u0430\u0447\u0435\u0441\u0442\u0432\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c regular expressions \u0438\u0437 JDK, \u043d\u0430\u0448 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0441 \u0442\u043e\u043a\u0435\u043d\u0438\u0437\u0430\u0446\u0438\u0435\u0439 (custom) \u0438, \u043d\u0430\u043a\u043e\u043d\u0435\u0446, BitNFA.<\/p>\n<p>\u041f\u0435\u0440\u0432\u0430\u044f \u043f\u0430\u0440\u0430 \u2014 <strong>BitNFA vs custom<\/strong>, \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u0443\u043a\u0430\u0437\u0430\u043d\u043e \u0441\u043e\u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0435\u0439 \u0432 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u0445 \u0432 \u0441\u0435\u043a\u0443\u043d\u0434\u0443 (speedup). \u0422\u043e \u0435\u0441\u0442\u044c, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, 2,269 \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e BitNFA \u0432 \u0434\u0432\u0430 \u0441 \u043b\u0438\u0448\u043d\u0438\u043c \u0440\u0430\u0437\u0430 \u0431\u044b\u0441\u0442\u0440\u0435\u0435, \u0447\u0435\u043c custom.<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong>Pattern\/Input<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>first<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>second<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>third<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code>status*<\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">2,269<\/p>\n<\/td>\n<td>\n<p align=\"left\">3,134<\/p>\n<\/td>\n<td>\n<p align=\"left\">2,286<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code>duration*ms<\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">3,188<\/p>\n<\/td>\n<td>\n<p align=\"left\">6,065<\/p>\n<\/td>\n<td>\n<p align=\"left\">14,436<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code><em>tcsbank<\/em><\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">2,703<\/p>\n<\/td>\n<td>\n<p align=\"left\">4,082<\/p>\n<\/td>\n<td>\n<p align=\"left\">5,494<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u0412\u0438\u0434\u0438\u043c, \u0447\u0442\u043e \u043d\u0430\u0448 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432 2\u201412 \u0440\u0430\u0437 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435 \u2014 \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430 \u0438 \u0441\u0442\u0440\u043e\u043a\u0438. \u042d\u0442\u0430 \u043d\u0435\u0441\u0442\u0430\u0431\u0438\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u043d\u0430\u0441 \u0431\u0435\u0441\u043f\u043e\u043a\u043e\u0438\u043b\u0430 \u0438 \u043f\u0440\u0438\u0432\u0435\u043b\u0430 \u043a \u043f\u043e\u0438\u0441\u043a\u0443 \u043d\u043e\u0432\u044b\u0445 \u0440\u0435\u0448\u0435\u043d\u0438\u0439. \u041c\u043e\u0436\u043d\u043e \u043e\u0446\u0435\u043d\u0438\u0442\u044c \u0442\u0438\u043f\u043e\u0432\u0443\u044e \u0440\u0430\u0437\u043d\u0438\u0446\u0443 \u0432 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0447\u0435\u0440\u0435\u0437 \u0433\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0435, \u043f\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044e \u0441 custom \u043e\u043d\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u0438\u0442 4,021 \u0440\u0430\u0437\u0430.<\/p>\n<p>\u0412\u0442\u043e\u0440\u0430\u044f \u043f\u0430\u0440\u0430 \u2014 BitNFA vs \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f \u0438\u0437 JDK, \u0447\u0438\u0441\u043b\u0430\u043c\u0438 \u043f\u043e\u043a\u0430\u0437\u0430\u043d\u043e \u043e\u0442\u043d\u043e\u0448\u0435\u043d\u0438\u0435 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0435\u0439.<\/p>\n<div>\n<div class=\"table\">\n<table>\n<tbody>\n<tr>\n<td>\n<p align=\"left\"><strong>Pattern\/Input<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>first<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>second<\/strong><\/p>\n<\/td>\n<td>\n<p align=\"left\"><strong>third<\/strong><\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code>status*<\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">3,000<\/p>\n<\/td>\n<td>\n<p align=\"left\">5,715<\/p>\n<\/td>\n<td>\n<p align=\"left\">5,785<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code>duration*ms<\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">5,762<\/p>\n<\/td>\n<td>\n<p align=\"left\">5,574<\/p>\n<\/td>\n<td>\n<p align=\"left\">5,659<\/p>\n<\/td>\n<\/tr>\n<tr>\n<td>\n<p align=\"left\"><code><em>tcsbank<\/em><\/code><\/p>\n<\/td>\n<td>\n<p align=\"left\">132,755<\/p>\n<\/td>\n<td>\n<p align=\"left\">3,192<\/p>\n<\/td>\n<td>\n<p align=\"left\">4,238<\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/div>\n<\/div>\n<p>\u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u0441 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u043c\u0438 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u043c\u0438 \u0438\u043d\u043e\u0433\u0434\u0430 \u0434\u0430\u0436\u0435 \u043d\u0435\u0443\u0434\u043e\u0431\u043d\u043e: \u0441 \u043d\u0438\u043c\u0438 \u0441\u043b\u0443\u0447\u0430\u044e\u0442\u0441\u044f \u043a\u0430\u0442\u0430\u0441\u0442\u0440\u043e\u0444\u0438\u0447\u0435\u0441\u043a\u0438\u0435 \u043f\u0430\u0434\u0435\u043d\u0438\u044f \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043f\u0440\u0438 \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u0435\u043a. \u0412 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043a\u0438 \u0432 132 \u0440\u0430\u0437\u0430 \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u0435\u0435, \u0447\u0435\u043c BitNFA, \u0438 \u044d\u0442\u043e \u0442\u043e\u043b\u044c\u043a\u043e \u0434\u0432\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0438! \u0422\u0430\u043a\u043e\u0435 \u043d\u0435 \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u0434\u043b\u044f \u043d\u0430\u0433\u0440\u0443\u0436\u0435\u043d\u043d\u043e\u0433\u043e \u0434\u0432\u0438\u0436\u043a\u0430 \u043f\u043e\u0438\u0441\u043a\u0430, \u0433\u0434\u0435 \u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u0435\u043b\u0438 \u0437\u0430\u0447\u0430\u0441\u0442\u0443\u044e \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u044e\u0442 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u043f\u0440\u043e\u0441\u044b. \u0413\u0435\u043e\u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u2014 6,831.<\/p>\n<h2>\u041e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0438\u044f<\/h2>\n<p>\u0418 \u0432\u043e\u0442 \u043a\u043e\u043d\u043a\u0443\u0440\u0435\u043d\u0442\u044b \u0434\u0430\u043b\u0435\u043a\u043e \u043f\u043e\u0437\u0430\u0434\u0438, \u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0441\u0430\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u0440\u0430\u0437\u0434\u043d\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u0431\u0435\u0434\u0443. \u041d\u043e \u0435\u0441\u0442\u044c \u043d\u044e\u0430\u043d\u0441: BitNFA \u0432 \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u043e\u043c \u0432\u0438\u0434\u0435 \u043e\u0433\u0440\u0430\u043d\u0438\u0447\u0435\u043d\u0430 ASCII-\u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438 \u0438 \u0448\u0430\u0431\u043b\u043e\u043d \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0434\u043b\u0438\u043d\u043d\u0435\u0435 62 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 (64 \u043c\u0438\u043d\u0443\u0441 2 \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u2014 \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u044b\u0439 \u0438 \u043a\u043e\u043d\u0446\u0435\u0432\u043e\u0439 \u043f\u0440\u043e\u0431\u0435\u043b\u044b). \u041d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435 60 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0431\u043e\u043b\u0435\u0435 \u0447\u0435\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e, \u043d\u043e \u043f\u0440\u0438\u0445\u043e\u0434\u0438\u0442\u0441\u044f \u0434\u0435\u043b\u0430\u0442\u044c \u0444\u043e\u043b\u043b\u0431\u044d\u043a.<\/p>\n<p>\u0422\u0430\u043a, \u0430 \u0447\u0442\u043e \u0442\u0430\u043c \u0441 \u044e\u043d\u0438\u043a\u043e\u0434\u043e\u043c? \u041a\u0440\u0430\u0442\u043a\u043e \u0433\u043e\u0432\u043e\u0440\u044f, \u0434\u043b\u044f \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u043a\u0438 \u043f\u043e\u043b\u043d\u043e\u0433\u043e UTF-8 \u043d\u0443\u0436\u043d\u043e \u0434\u0435\u043a\u043e\u0434\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0431\u0430\u0439\u0442\u044b \u043a\u043e\u0434\u0438\u0440\u043e\u0432\u043a\u0438 (codeunit) \u0432 \u0430\u0431\u0441\u0442\u0440\u0430\u043a\u0442\u043d\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b (codepoint). Code point \u2014 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u0430 \u0438\u0437 \u0434\u0438\u0430\u043f\u0430\u0437\u043e\u043d\u0430 [0, 1114111], \u0438 \u043f\u043e\u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u0430\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u0430 \u0434\u043b\u044f \u0445\u0440\u0430\u043d\u0435\u043d\u0438\u044f \u043c\u0430\u0441\u043e\u043a \u043f\u0440\u0438 \u0442\u0430\u043a\u043e\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u0435 \u0430\u043b\u0444\u0430\u0432\u0438\u0442\u0430. \u042d\u0442\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, <a href=\"https:\/\/icu-project.org\/docs\/papers\/foldedtrie_iuc21.ppt\">\u0443\u043f\u0430\u043a\u043e\u0432\u044b\u0432\u0430\u044e\u0442 \u0432 trie<\/a>, \u0442\u043e \u0435\u0441\u0442\u044c \u0434\u0435\u043b\u0430\u044e\u0442 <a href=\"https:\/\/www.unicode.org\/versions\/Unicode16.0.0\/core-spec\/chapter-5\/#G11079\">\u043c\u043d\u043e\u0433\u043e\u0441\u0442\u0430\u0434\u0438\u0439\u043d\u044b\u043c\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0430\u043c\u0438.<\/a>\u00a0<\/p>\n<p>\u041c\u044b \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0435\u0440\u0432\u044b\u0439 plane \u0438\u0437 \u0432\u0441\u0435\u0433\u043e Unicode, \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0443\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u044f\u0441\u044c \u0432 64 \u0442\u044b\u0441\u044f\u0447\u0438 \u0437\u0430\u043f\u0438\u0441\u0435\u0439 \u0432 \u0442\u0430\u0431\u043b\u0438\u0446\u0435, \u0442\u043e \u0435\u0441\u0442\u044c \u0441 \u0440\u0443\u0441\u0441\u043a\u0438\u043c \u044f\u0437\u044b\u043a\u043e\u043c, \u043d\u043e \u0431\u0435\u0437 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u043a\u0438 \u044d\u043c\u043e\u0434\u0437\u0438. \u0412 \u0434\u0435\u0439\u0441\u0442\u0432\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043c\u044b \u043f\u0435\u0440\u0435\u0439\u0434\u0435\u043c \u043d\u0430 folded trie, \u043a\u0430\u043a \u0442\u043e\u043b\u044c\u043a\u043e \u0442\u0430\u043a\u0430\u044f \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u044c \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0435\u0442.<\/p>\n<h2>\u0418\u0442\u043e\u0433\u0438 \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u0443\u0442\u0438<\/h2>\n<p>\u0412\u0437\u044f\u0432 \u0437\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0433\u0438\u0431\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438, \u043c\u044b \u0441\u043c\u043e\u0433\u043b\u0438 \u043f\u043e\u044d\u0442\u0430\u043f\u043d\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u0442\u044c \u0435\u0433\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u0438 \u0434\u0430\u043b\u0435\u043a\u043e \u0437\u0430 \u043f\u0440\u0435\u0434\u0435\u043b\u044b \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u043e\u043d\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u0438. \u041a\u0430\u0436\u0434\u044b\u0439 \u0448\u0430\u0433 \u043f\u043e-\u0441\u0432\u043e\u0435\u043c\u0443 \u043f\u0440\u043e\u0441\u0442, \u043d\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432, \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438 \u0438, \u0433\u043b\u0430\u0432\u043d\u043e\u0435, \u043d\u0430\u0446\u0435\u043b\u0435\u043d\u043d\u043e\u0441\u0442\u0438 \u043d\u0430 \u0440\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442.\u00a0<\/p>\n<p>\u0412\u0441\u0435\u0433\u0434\u0430 \u0441\u0442\u043e\u0438\u0442 \u0432\u043e\u043f\u0440\u043e\u0441: \u0430 \u043c\u043e\u0436\u043d\u043e \u043b\u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435, \u043d\u0435 \u043f\u043e\u0442\u0435\u0440\u044f\u0432 \u043f\u0440\u0438 \u044d\u0442\u043e\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438, \u0432\u0435\u0434\u044c \u043e\u043d\u0430 \u0438 \u0435\u0441\u0442\u044c \u043c\u0435\u0440\u0438\u043b\u043e \u043b\u044e\u0431\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430? \u0411\u0435\u0437 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0432\u043e\u043f\u0440\u043e\u0441\u0430 \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u043b\u044e\u0431\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u2014 \u044d\u0442\u043e \u043b\u0438\u0448\u044c \u0435\u0449\u0435 \u043e\u0434\u0438\u043d \u0441\u043f\u043e\u0441\u043e\u0431 \u0440\u0435\u0448\u0438\u0442\u044c \u0437\u0430\u0434\u0430\u0447\u0443, \u043e\u0434\u0438\u043d \u0438\u0437 \u043c\u043d\u043e\u0433\u0438\u0445 \u0438, \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e, \u043d\u0435\u0430\u043a\u0442\u0443\u0430\u043b\u044c\u043d\u044b\u0439 \u043d\u0430 \u043f\u0440\u0430\u043a\u0442\u0438\u043a\u0435.\u00a0<\/p>\n<p>\u041f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0439 \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0437\u043c \u2014 \u044d\u0442\u043e \u043a\u043b\u0430\u0434\u0435\u0437\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0438 \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440 \u0434\u0430\u043d\u043d\u044b\u0445, \u043a\u043e\u0442\u043e\u0440\u044b\u0439, \u044f \u0443\u0432\u0435\u0440\u0435\u043d, \u0435\u0449\u0435 \u043d\u0435 \u0440\u0430\u0437 \u043f\u0440\u0435\u043f\u043e\u0434\u043d\u0435\u0441\u0435\u0442 \u043d\u0430\u043c \u043d\u043e\u0432\u044b\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0432 \u0441\u0430\u043c\u044b\u0445 \u0440\u0430\u0437\u043d\u044b\u0445 \u043e\u0431\u043b\u0430\u0441\u0442\u044f\u0445. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0434\u043b\u044f \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u043c\u043e\u0449\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c <a href=\"https:\/\/docs.rs\/bndm\/latest\/bndm\/\">BNDM<\/a>, \u0434\u043e\u0441\u0442\u0443\u043f\u043d\u044b\u0439 \u0438 \u0434\u043b\u044f \u0434\u0440\u0443\u0433\u0438\u0445 \u044f\u0437\u044b\u043a\u043e\u0432 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f. \u041e\u0442\u043a\u0440\u044b\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u043e\u0438\u0441\u043a \u0442\u0430\u043a\u0438\u0445 \u0433\u0438\u0431\u0440\u0438\u0434\u043e\u0432 \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 \u0438 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u0430\u0440\u0430\u043b\u043b\u0435\u043b\u0438\u0437\u043c\u0430.<\/p>\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\/906990\/\"> https:\/\/habr.com\/ru\/articles\/906990\/<\/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<figure class=\"full-width\"><\/figure>\n<p>\u041c\u0435\u043d\u044f \u0437\u043e\u0432\u0443\u0442 \u0414\u043c\u0438\u0442\u0440\u0438\u0439 \u041e\u043b\u044c\u0448\u0430\u043d\u0441\u043a\u0438\u0439, \u044f \u0432\u0435\u0434\u0443\u0449\u0438\u0439 \u0438\u043d\u0436\u0435\u043d\u0435\u0440 \u0422-\u0411\u0430\u043d\u043a\u0430. \u0420\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u043d\u043e\u0432\u043e\u043c (\u043d\u0430\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u043c\u043d\u0435 \u0438\u0437\u0432\u0435\u0441\u0442\u043d\u043e) \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u0435\u043a\u0441\u0442\u0430 \u043f\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0443. \u0422\u0430\u043a\u0430\u044f \u0437\u0430\u0434\u0430\u0447\u0430 \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u0432 \u0440\u0430\u043c\u043a\u0430\u0445 \u043f\u0440\u043e\u0435\u043a\u0442\u0430 <a href=\"https:\/\/sage-observability.tech\/\">Sage<\/a> \u2014 observability-\u043f\u043b\u0430\u0442\u0444\u043e\u0440\u043c\u044b \u043e\u0442 \u0422-\u0411\u0430\u043d\u043a\u0430, \u0434\u043b\u044f \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043c\u044b \u0441\u0442\u0440\u043e\u0438\u043c \u043d\u043e\u0432\u044b\u0439 \u0431\u044d\u043a\u044d\u043d\u0434 \u0434\u043b\u044f \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043b\u043e\u0433\u043e\u0432, <a href=\"https:\/\/ecode.ozon.tech\/archive\/E%E2%80%93Code%202024\/talks\/d19c95082dc1419685ff9ad9da240a23\/?__rr=1&amp;abt_att=1\">SageDB.<\/a>\u00a0<\/p>\n<h2>\u041a\u0430\u043a\u0430\u044f \u0431\u044b\u043b\u0430 \u0437\u0430\u0434\u0430\u0447\u0430<\/h2>\n<p>\u0418\u043c\u0435\u044f, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0437\u0430\u043f\u0440\u043e\u0441 hello *orld, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0431\u044b\u043b\u043e \u043d\u0430\u0439\u0442\u0438 \u0441\u0442\u0440\u043e\u043a\u0438, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0438\u0435 \u043a\u0430\u043a hello world, \u0442\u0430\u043a \u0438 hello, wonderful world, \u2014 \u0442\u043e \u0435\u0441\u0442\u044c \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0430 \u043f\u043e\u0434\u0440\u0430\u0437\u0443\u043c\u0435\u0432\u0430\u0435\u0442 \u043b\u044e\u0431\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0438 \u043c\u044b \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u0435\u043c \u0437\u043d\u0430\u043a\u0438 \u043f\u0440\u0435\u043f\u0438\u043d\u0430\u043d\u0438\u044f.\u00a0<\/p>\n<p>\u0414\u043b\u044f \u0442\u0440\u0430\u0434\u0438\u0446\u0438\u043e\u043d\u043d\u044b\u0445 \u043f\u043e\u0434\u0445\u043e\u0434\u043e\u0432 \u0441 \u0442\u043e\u043a\u0435\u043d\u0438\u0437\u0430\u0446\u0438\u0435\u0439 \u044d\u0442\u043e \u0432\u044b\u043b\u0438\u0432\u0430\u0435\u0442\u0441\u044f \u0432 \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b: \u043d\u0443\u0436\u043d\u043e \u0441\u043e\u0431\u0440\u0430\u0442\u044c \u0432\u0441\u0435 \u0442\u043e\u043a\u0435\u043d\u044b, \u043e\u043a\u0430\u043d\u0447\u0438\u0432\u0430\u044e\u0449\u0438\u0435\u0441\u044f \u043d\u0430 orld, \u0438 \u0438\u043c\u0435\u0442\u044c \u0432 \u0432\u0438\u0434\u0443 \u043f\u0440\u043e\u043f\u0443\u0441\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u043b\u044c\u043d\u043e\u0433\u043e \u0447\u0438\u0441\u043b\u0430 \u0442\u043e\u043a\u0435\u043d\u043e\u0432 \u043c\u0435\u0436\u0434\u0443 hello \u0438 \u043a\u043e\u043d\u0446\u0435\u0432\u044b\u043c \u0442\u043e\u043a\u0435\u043d\u043e\u043c. \u0411\u043e\u043b\u044c\u0448\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u0435\u043a \u2014 \u0431\u043e\u043b\u044c\u0448\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c.\u00a0<\/p>\n<p>\u0412 SageDB \u043c\u044b \u0441\u043e\u0437\u043d\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043e\u0442\u0445\u043e\u0434\u0438\u043c \u043e\u0442 \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u044f \u043f\u043e\u043b\u043d\u044b\u0445 inverted index \u0438 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c brute-force-\u0442\u0430\u043a\u0442\u0438\u043a\u0443 \u2014 \u0438\u0449\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d \u043f\u043e \u0432\u0441\u0435\u043c \u043e\u0442\u0444\u0438\u043b\u044c\u0442\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0441\u0442\u0440\u043e\u043a\u0430\u043c.<\/p>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u0432\u043e\u0437\u043d\u0438\u043a\u043b\u0430 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u0442\u0435\u043a\u0441\u0442\u0430 \u043f\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c, \u043f\u0435\u0440\u0432\u043e\u0435, \u0447\u0442\u043e \u043f\u0440\u0438\u0448\u043b\u043e \u0432 \u0433\u043e\u043b\u043e\u0432\u0443, \u2014 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0435 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0428\u0430\u0431\u043b\u043e\u043d hello <em>orld \u043c\u043e\u0436\u043d\u043e \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043a\u0430\u043a \\bhello\\s+.<\/em>orld\\b, \u0434\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0441\u043b\u043e\u0432\u0430 \u0440\u0430\u0437\u0434\u0435\u043b\u0435\u043d\u044b \u043f\u0440\u043e\u0431\u0435\u043b\u0430\u043c\u0438.\u00a0<\/p>\n<p>\u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u044f \u0435\u0449\u0435 \u0438 \u0430\u0432\u0442\u043e\u0440 <a href=\"https:\/\/dlang.org\/phobos\/std_regex.html\">std.regex-\u043c\u043e\u0434\u0443\u043b\u044f \u044f\u0437\u044b\u043a\u0430 D<\/a>, \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b \u0442\u0430\u043a\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430 \u043c\u0435\u043d\u044f \u043d\u0435 \u0441\u0438\u043b\u044c\u043d\u043e \u0443\u0434\u0438\u0432\u0438\u043b\u0438: \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e \u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043d\u0430\u043a\u043b\u0430\u0434\u043d\u044b\u0435 \u0440\u0430\u0441\u0445\u043e\u0434\u044b \u043d\u0430 \u0437\u0430\u043f\u0443\u0441\u043a \u0434\u0432\u0438\u0436\u043a\u0430 \u043d\u0430 \u043e\u0442\u0434\u0435\u043b\u044c\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a\u0430\u0445.\u00a0<\/p>\n<p>\u0414\u0430\u0436\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u043d\u0438\u0435 <a href=\"https:\/\/github.com\/intel\/hyperscan\">Hyperscan<\/a> \u043d\u0435 \u0434\u0430\u043b\u043e \u0436\u0435\u043b\u0430\u0435\u043c\u043e\u0439 \u0441\u043a\u043e\u0440\u043e\u0441\u0442\u0438 \u0440\u0430\u0431\u043e\u0442\u044b \u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u043b\u043e \u043f\u0440\u043e\u0431\u043b\u0435\u043c \u0438\u043d\u0442\u0435\u0433\u0440\u0430\u0446\u0438\u0438 \u0441 JVM, \u0442\u0430\u043a \u043a\u0430\u043a \u043d\u0430\u0448 \u0434\u0432\u0438\u0436\u043e\u043a \u043d\u0430\u043f\u0438\u0441\u0430\u043d \u043d\u0430 Java. \u041f\u043b\u0430\u0442\u0430 \u0437\u0430 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0430\u043b\u044c\u043d\u043e\u0441\u0442\u044c \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0432\u044b\u0441\u043e\u043a\u0430 \u0438 \u043c\u044b \u0440\u0435\u0448\u0438\u043b\u0438 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u0435 \u0438 \u0431\u044b\u0441\u0442\u0440\u044b\u0435 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0442\u0430\u043c, \u0433\u0434\u0435 \u044d\u0442\u043e \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e.\u00a0<\/p>\n<p>\u0422\u0430\u043a \u043f\u043e\u044f\u0432\u0438\u043b\u0430\u0441\u044c \u0438\u0434\u0435\u044f \u0432\u0437\u044f\u0442\u044c \u0437\u0430 \u043e\u0441\u043d\u043e\u0432\u0443 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c Shift-Or \u0438 \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u0438\u0431\u043b\u0438\u0437\u0438\u0442\u044c\u0441\u044f \u043a \u043d\u0430\u0448\u0438\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u0430\u043c. \u042d\u0442\u043e \u0431\u044b\u043b \u043f\u0443\u0442\u044c \u044d\u043a\u0441\u043f\u0435\u0440\u0438\u043c\u0435\u043d\u0442\u043e\u0432, \u0438 \u043f\u043e\u0441\u0442\u0435\u043f\u0435\u043d\u043d\u043e \u043c\u043d\u0435 \u0443\u0434\u0430\u043b\u043e\u0441\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u0440\u0438\u0431\u043b\u0438\u0436\u0435\u043d\u043d\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435, \u043d\u043e \u0438 \u0432\u043e\u0432\u0441\u0435 \u0443\u043b\u043e\u0436\u0438\u0442\u044c \u0432\u0441\u044e \u043b\u043e\u0433\u0438\u043a\u0443 \u043d\u0430\u0448\u0438\u0445 \u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u044f \u043d\u0430\u0437\u044b\u0432\u0430\u043b <abbr class=\"habraabbr\" title=\"NFA - Nondeterministic Finite-state Automaton\" data-title=\"&lt;p&gt;NFA - Nondeterministic Finite-state Automaton&lt;\/p&gt;\" data-abbr=\"BitNFA.\">BitNFA.<\/abbr> \u041f\u043e\u043a\u0430\u0436\u0443 \u043d\u0430\u0448 \u043f\u0443\u0442\u044c \u043f\u043e \u0448\u0430\u0433\u0430\u043c \u0438 \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443, \u043a\u0430\u043a \u0438\u0437 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0438\u0434\u0435\u0438 \u043f\u043e\u044f\u0432\u0438\u043b\u0441\u044f \u043d\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c.<\/p>\n<h2>\u041d\u0430\u0447\u0430\u043b\u043e \u2014 Shift-Or<\/h2>\n<p>\u0421\u043d\u0430\u0447\u0430\u043b\u0430 \u0440\u0430\u0437\u0431\u0435\u0440\u0435\u043c\u0441\u044f \u0441 \u0441\u0430\u043c\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u043c Shift-Or. \u0412 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u043f\u043e \u044d\u0442\u043e\u0439 \u0442\u0435\u043c\u0435, \u043a\u0430\u043a \u043c\u043d\u0435 \u043a\u0430\u0436\u0435\u0442\u0441\u044f, \u0441\u043b\u0438\u0448\u043a\u043e\u043c \u0443\u0432\u043b\u0435\u043a\u0430\u044e\u0442\u0441\u044f \u0434\u0432\u043e\u0438\u0447\u043d\u044b\u043c\u0438 \u043c\u0430\u0442\u0440\u0438\u0446\u0430\u043c\u0438, \u0443\u043f\u0443\u0441\u043a\u0430\u044f \u0433\u043b\u0430\u0432\u043d\u044b\u0439 \u043c\u043e\u043c\u0435\u043d\u0442: \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0430 \u0441\u0430\u043c\u043e\u043c \u0434\u0435\u043b\u0435 \u0447\u0430\u0441\u0442\u043d\u044b\u0439 \u0441\u043b\u0443\u0447\u0430\u0439 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e NFA. \u0422\u0430\u043a \u0447\u0442\u043e \u043b\u0443\u0447\u0448\u0438\u0439 \u0441\u043f\u043e\u0441\u043e\u0431 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u0442\u044c\u0441\u044f \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0435 \u2014 \u044d\u0442\u043e \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u043a\u0430\u043a \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 NFA, \u0430 \u0437\u0430\u0442\u0435\u043c \u0443\u0436\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0431\u0438\u0442\u0430\u043c.\u00a0<\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0432\u043e\u0437\u044c\u043c\u0435\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 ababc \u0438 \u043f\u043e\u0441\u0442\u0440\u043e\u0438\u043c \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0434\u043b\u044f \u0435\u0435 \u043f\u043e\u0438\u0441\u043a\u0430. \u0423 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043e\u0434\u043d\u043e \u0441\u0442\u0430\u0440\u0442\u043e\u0432\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0432\u0441\u0435\u0433\u0434\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u043e, \u2014 \u0442\u0430\u043a \u043c\u044b \u00ab\u043f\u0440\u0438\u043a\u043b\u0430\u0434\u044b\u0432\u0430\u0435\u043c\u00bb \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u043a \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 \u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u043c \u0442\u0435\u043a\u0441\u0442\u0435. \u0414\u0430\u043b\u0435\u0435 \u0441\u043b\u0435\u0434\u0443\u0435\u0442 \u0446\u0435\u043f\u043e\u0447\u043a\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u043f\u043e \u043e\u0434\u043d\u043e\u043c\u0443 \u043d\u0430 \u043a\u0430\u0436\u0434\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438, \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u0431\u0443\u0434\u0443\u0442 \u043e\u0431\u043e\u0437\u043d\u0430\u0447\u0435\u043d\u044b \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u043c, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043c\u044b \u043e\u0436\u0438\u0434\u0430\u0435\u043c \u0443\u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e\u0431\u044b \u043f\u0435\u0440\u0435\u0439\u0442\u0438 \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435. \u041d\u0430\u043a\u043e\u043d\u0435\u0446, \u0435\u0441\u0442\u044c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u2014 \u0435\u0441\u043b\u0438 \u043e\u043d\u043e \u0441\u0442\u0430\u043b\u043e \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u043f\u043e\u0441\u043b\u0435 \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430, \u043c\u044b \u043d\u0430\u0448\u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443.<\/p>\n<p>\u0412 \u0447\u0435\u043c \u0436\u0435 \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0441\u0442\u044c \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430? \u041f\u0440\u043e\u0441\u0442\u043e\u0439 \u043e\u0442\u0432\u0435\u0442 \u2014 \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e \u043c\u043e\u0433\u0443\u0442 \u0431\u044b\u0442\u044c \u0430\u043a\u0442\u0438\u0432\u043d\u044b \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439. \u0422\u0430\u043a\u0430\u044f \u0441\u0438\u0442\u0443\u0430\u0446\u0438\u044f \u043c\u043e\u0436\u0435\u0442 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u0443\u0442\u044c \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 abababc. \u041f\u043e\u0441\u043b\u0435 \u0442\u043e\u0433\u043e \u043a\u0430\u043a \u043c\u044b \u043f\u0440\u043e\u0447\u0438\u0442\u0430\u043b\u0438 ab, \u043c\u044b \u0441\u043d\u043e\u0432\u0430 \u0432\u0438\u0434\u0438\u043c a \u2014 \u0438 \u0437\u0430\u0440\u0430\u043d\u0435\u0435 \u043d\u0435 \u0437\u043d\u0430\u0435\u043c, \u0431\u0443\u0434\u0435\u0442 \u043b\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043d\u0430\u0439\u0434\u0435\u043d\u0430 \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043f\u0435\u0440\u0432\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 a \u0438\u043b\u0438 \u0441\u043e \u0432\u0442\u043e\u0440\u043e\u0433\u043e. \u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0442\u043e\u0436\u0435 \u044d\u0442\u043e\u0433\u043e \u00ab\u043d\u0435 \u0437\u043d\u0430\u0435\u0442\u00bb \u0438 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u0434\u0432\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u043e\u0442\u0440\u0430\u0436\u0430\u044e\u0449\u0438\u0445 \u044d\u0442\u043e\u0442 \u043d\u0435\u0434\u0435\u0442\u0435\u0440\u043c\u0438\u043d\u0438\u0437\u043c.\u00a0<\/p>\n<p>\u041f\u0440\u043e\u0446\u0435\u0441\u0441 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u0438 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u0440\u043e\u0441\u0442: \u043c\u044b \u0441\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u043c \u043e\u0447\u0435\u0440\u0435\u0434\u043d\u043e\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u0438 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u0438 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432. \u0415\u0441\u043b\u0438 \u0435\u0441\u0442\u044c \u0434\u043e\u043f\u0443\u0441\u0442\u0438\u043c\u044b\u0439 \u043f\u0435\u0440\u0435\u0445\u043e\u0434, \u043c\u044b \u043f\u0435\u0440\u0435\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0432\u043f\u0435\u0440\u0435\u0434. \u0412 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0430\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438\u0441\u0447\u0435\u0437\u0430\u0435\u0442.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430<\/figcaption><\/div>\n<\/figure>\n<p>\u041f\u043e\u0438\u0441\u043a \u0447\u0435\u0440\u0435\u0437 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0434\u043e\u0432\u043e\u043b\u044c\u043d\u043e \u0438\u0437\u044f\u0449\u0435\u043d, \u043d\u043e \u0442\u0440\u0435\u0431\u0443\u0435\u0442 \u0433\u0434\u0435-\u0442\u043e \u0445\u0440\u0430\u043d\u0438\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0438 \u0432 \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0431\u0443\u0434\u0435\u0442 \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u043c\u0435\u0434\u043b\u0435\u043d\u043d\u043e: \u0437\u0430 O(mn), \u0433\u0434\u0435 m \u2014 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0432 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0435, \u0430 n \u2014 \u0440\u0430\u0437\u043c\u0435\u0440 \u0442\u0435\u043a\u0441\u0442\u0430.\u00a0<\/p>\n<p>\u0421\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u044e\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u043c\u0435\u0442\u043e\u0434\u0438\u043a\u0438 \u0443\u0441\u043a\u043e\u0440\u0435\u043d\u0438\u044f NFA, \u043d\u043e \u043f\u043e-\u043d\u0430\u0441\u0442\u043e\u044f\u0449\u0435\u043c\u0443 \u043a\u0440\u0430\u0441\u0438\u0432\u043e\u0435 \u0440\u0435\u0448\u0435\u043d\u0438\u0435 \u0434\u043b\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0445 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u2014 \u044d\u0442\u043e Shift-Or. \u041f\u043e\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043d\u0430 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0430\u0448\u0435\u0433\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0438 \u0441\u043e\u043f\u043e\u0441\u0442\u0430\u0432\u0438\u043c \u043a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0447\u0438\u0441\u043b\u043e \u043f\u043e \u043f\u043e\u0440\u044f\u0434\u043a\u0443 \u0441\u043b\u0435\u0434\u043e\u0432\u0430\u043d\u0438\u044f. \u0422\u0435\u043f\u0435\u0440\u044c \u0435\u0441\u043b\u0438 \u0447\u0438\u0441\u043b\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043c\u0435\u043d\u044c\u0448\u0435 64 (\u0434\u043b\u044f 64-\u0431\u0438\u0442\u043d\u044b\u0445 \u0441\u0438\u0441\u0442\u0435\u043c, 32 \u0434\u043b\u044f 32-\u0431\u0438\u0442\u043d\u044b\u0445), \u0442\u043e \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043e\u043f\u0438\u0441\u0430\u0442\u044c \u043b\u044e\u0431\u0443\u044e \u043a\u043e\u043c\u0431\u0438\u043d\u0430\u0446\u0438\u044e \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u043a\u0430\u043a \u043e\u0434\u043d\u043e \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e. \u041a\u0430\u0436\u0434\u043e\u043c\u0443 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u0434\u0430\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0431\u0438\u0442: 0 \u0431\u0443\u0434\u0435\u0442 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0430 1 \u2014 \u043d\u0435\u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435\u043c. \u041d\u0430 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c \u0440\u0438\u0441\u0443\u043d\u043a\u0435 \u0431\u0443\u0434\u0435\u043c \u0441\u0447\u0438\u0442\u0430\u0442\u044c, \u0447\u0442\u043e \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u0443\u0436\u0435 \u043f\u0440\u043e\u0448\u0435\u043b \u0447\u0435\u0440\u0435\u0437 abab \u0438 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438 \u043e\u0441\u0442\u0430\u043b\u0438\u0441\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f 1 \u0438 3.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0431\u0438\u0442\u0430\u043c \u0432 \u0441\u043b\u043e\u0432\u0435<\/figcaption><\/div>\n<\/figure>\n<p>\u041a\u043e\u0433\u0434\u0430 \u0443 \u043d\u0430\u0441 \u043f\u043e\u044f\u0432\u0438\u043b\u043e\u0441\u044c \u0442\u0430\u043a\u043e\u0435 \u043a\u043e\u043c\u043f\u0430\u043a\u0442\u043d\u043e\u0435 \u043e\u043f\u0438\u0441\u0430\u043d\u0438\u0435 \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439, \u043e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0438\u0439 \u0448\u0430\u0433 \u2014 \u0441\u0438\u043c\u0443\u043b\u044f\u0446\u0438\u044e \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438. \u041b\u0435\u0433\u043a\u043e \u0437\u0430\u043c\u0435\u0442\u0438\u0442\u044c, \u0447\u0442\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u044b\u0439 \u0441\u0434\u0432\u0438\u0433 \u043f\u0435\u0440\u0435\u0432\u0435\u0434\u0435\u0442 \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0440\u0430\u0437\u043e\u043c \u0432\u043f\u0435\u0440\u0435\u0434.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0441\u0434\u0432\u0438\u0433\u0443 \u0432\u0441\u0435\u0445 \u0431\u0438\u0442 \u043d\u0430 1<\/figcaption><\/div>\n<\/figure>\n<p>\u041e\u0441\u0442\u0430\u0435\u0442\u0441\u044f \u043e\u0442\u0444\u0438\u043b\u044c\u0442\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0434\u043e\u043b\u0436\u043d\u044b \u043e\u0441\u0442\u0430\u0442\u044c\u0441\u044f \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c\u0438. \u0414\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0435\u043a\u0440\u0430\u0441\u043d\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0438\u0442 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418\u041b\u0418 \u0441 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u043c\u0430\u0441\u043a\u043e\u0439 \u2014 \u043e\u043d\u0430, \u043a\u043e\u043d\u0435\u0447\u043d\u043e, \u0434\u043b\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u0441\u0432\u043e\u044f. \u0412\u0430\u0436\u043d\u043e \u0442\u043e, \u0447\u0442\u043e \u043c\u044b \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0435\u043c \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439, \u0442\u0430\u043a \u0447\u0442\u043e \u043f\u043e\u0441\u0442\u0440\u043e\u0435\u043d\u0438\u0435 \u044d\u0442\u0438\u0445 \u043c\u0430\u0441\u043e\u043a \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u044b \u0434\u043b\u044f \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430.<\/p>\n<p>\u0412 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0434\u043b\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 a \u0438 b \u0435\u0441\u0442\u044c \u0434\u0432\u0430 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430, \u0438\u043c \u0431\u0443\u0434\u0435\u0442 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u043e\u0432\u0430\u0442\u044c \u0434\u0432\u0430 \u043d\u0443\u043b\u0435\u0432\u044b\u0445 \u0431\u0438\u0442\u0430 \u0432 \u043c\u0430\u0441\u043a\u0435, \u0442\u0430\u043a \u043c\u044b \u0441\u043e\u0445\u0440\u0430\u043d\u0438\u043c \u043d\u0443\u043b\u0438 \u043f\u0440\u0438 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u043c\u0430\u0441\u043a\u0438 \u0447\u0435\u0440\u0435\u0437 \u0418\u041b\u0418.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u041f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0438\u043c, \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0439 \u0441\u0438\u043c\u0432\u043e\u043b \u2014 \u00ab\u0430\u00bb <\/figcaption><\/div>\n<\/figure>\n<figure class=\"full-width\">\n<div><figcaption>\u0410\u0432\u0442\u043e\u043c\u0430\u0442 \u0432 \u043a\u043e\u0440\u0440\u0435\u043a\u0442\u043d\u043e\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0438 \u043f\u043e\u0441\u043b\u0435 \u0447\u0442\u0435\u043d\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 \u00ab\u0430\u00bb\u00a0<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u0442\u0430\u0434\u0438\u044e: \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0443 \u043d\u0430\u0441 \u2014 \u0434\u0432\u0430 \u043d\u0443\u043b\u044f \u0432 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u0445 1 \u0438 3 \u043f\u043e\u0441\u043b\u0435 \u043f\u0440\u0435\u0434\u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430 b.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0435\u0435 \u0442\u0440\u0435\u0442\u044c\u0435\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 b<\/figcaption><\/div>\n<\/figure>\n<p>\u0410\u043d\u0430\u043b\u043e\u0433\u0438\u0447\u043d\u043e \u0440\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0441\u0434\u0432\u0438\u0433 \u0431\u0438\u0442\u043e\u0432, \u0442\u0435\u043f\u0435\u0440\u044c \u0443 \u043d\u0430\u0441 \u0430\u043a\u0442\u0438\u0432\u043d\u043e \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430<\/figcaption><\/div>\n<\/figure>\n<p>\u0424\u0438\u043b\u044c\u0442\u0440\u0430\u0446\u0438\u044f \u0447\u0435\u0440\u0435\u0437 \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u0430 c.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u0441\u0434\u0432\u0438\u0433\u0430<\/figcaption><\/div>\n<\/figure>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u043f\u043e\u0441\u043b\u0435 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u044f \u043c\u0430\u0441\u043a\u0438<\/figcaption><\/div>\n<\/figure>\n<p>\u0424\u0438\u043d\u0430\u043b\u044c\u043d\u043e \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0431\u0438\u0442\u0430, \u043f\u0440\u0438 \u043f\u043e\u043f\u0430\u0434\u0430\u043d\u0438\u0438 \u043d\u0430 \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043f\u043e\u0438\u0441\u043a \u0443\u0441\u043f\u0435\u0448\u043d\u043e \u0437\u0430\u0432\u0435\u0440\u0448\u0430\u0435\u0442\u0441\u044f, \u0442\u0430\u043a\u043e\u0435 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u0438\u0442\u044c \u0447\u0435\u0440\u0435\u0437 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0435 \u0418 \u2014 \u0434\u043e\u043b\u0436\u0435\u043d \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c\u0441\u044f 0 \u043f\u0440\u0438 \u043d\u0430\u043b\u043e\u0436\u0435\u043d\u0438\u0438 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u043c\u0430\u0441\u043a\u0438. \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u0431\u0443\u0434\u0435\u043c \u043d\u0430\u0437\u044b\u0432\u0430\u0442\u044c \u043c\u0430\u0448\u0438\u043d\u043d\u043e\u0435 \u0441\u043b\u043e\u0432\u043e, \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0449\u0435\u0435 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442, \u043f\u0440\u043e\u0441\u0442\u043e \u0441\u043b\u043e\u0432\u043e\u043c.<\/p>\n<figure class=\"full-width\">\n<div><figcaption>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u0430 \u0432 \u0444\u0438\u043d\u0430\u043b\u044c\u043d\u043e\u0439 \u0441\u0442\u0430\u0434\u0438\u0438<\/figcaption><\/div>\n<\/figure>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0432 \u043f\u0441\u0435\u0432\u0434\u043e\u043a\u043e\u0434\u0435 \u0421\u0438-\u043f\u043e\u0434\u043e\u0431\u043d\u043e\u0433\u043e \u044f\u0437\u044b\u043a\u0430 \u2014 \u0435\u0433\u043e \u043d\u0435\u0441\u043b\u043e\u0436\u043d\u043e \u043f\u0440\u0438\u0432\u0435\u0441\u0442\u0438 \u0432 \u0440\u0435\u0430\u043b\u044c\u043d\u044b\u0439 \u043a\u043e\u0434 \u043d\u0430 \u0421\/\u0421++\/Java\/C#\/Rust. \u0413\u043b\u0430\u0432\u043d\u043e\u0435, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043e\u0434\u0438\u043d \u0440\u0430\u0437 \u0434\u043b\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438. \u0414\u0430\u043b\u0435\u0435 \u0441 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0442\u0430\u0431\u043b\u0438\u0446\u0435\u0439 \u0438 \u043c\u0430\u0441\u043a\u043e\u0439 \u0437\u0430\u0432\u0435\u0440\u0448\u0435\u043d\u0438\u044f \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043c\u043d\u043e\u0433\u043e\u043a\u0440\u0430\u0442\u043d\u043e \u0438 \u0432 \u0440\u0430\u0437\u043d\u044b\u0445 \u0441\u0442\u0440\u043e\u043a\u0430\u0445 \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0443\u0436\u043d\u0443\u044e \u043d\u0430\u043c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443.\u00a0<\/p>\n<p>\u041e\u0441\u043d\u043e\u0432\u043d\u043e\u0439 \u0446\u0438\u043a\u043b \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u043e \u043f\u0440\u044f\u043c\u043e\u043b\u0438\u043d\u0435\u0435\u043d \u0438 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0438\u0437 \u043e\u0434\u043d\u043e\u0433\u043e \u0447\u0442\u0435\u043d\u0438\u044f \u0442\u0430\u0431\u043b\u0438\u0446\u044b, \u043e\u0434\u043d\u043e\u0433\u043e \u0441\u0434\u0432\u0438\u0433\u0430 \u0432\u043b\u0435\u0432\u043e, \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418\u041b\u0418 \u0438 \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u0418. \u0422\u0430\u043a\u0438\u0435 \u043f\u043b\u043e\u0442\u043d\u044b\u0435 \u0446\u0438\u043a\u043b\u044b \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u0440\u0430\u0431\u043e\u0442\u0430\u044e\u0442 \u043d\u0430 \u0441\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u044b\u0445 \u043f\u0440\u043e\u0446\u0435\u0441\u0441\u043e\u0440\u0430\u0445, \u0438 \u043f\u0440\u0438 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e\u0441\u0442\u0438 \u0435\u0433\u043e \u043c\u043e\u0436\u043d\u043e \u0440\u0430\u0437\u043c\u043e\u0442\u0430\u0442\u044c (unroll), \u0447\u0442\u043e, \u0441\u043a\u043e\u0440\u0435\u0435 \u0432\u0441\u0435\u0433\u043e, \u0438 \u0441\u0434\u0435\u043b\u0430\u0435\u0442 \u043e\u043f\u0442\u0438\u043c\u0438\u0437\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043a\u043e\u043c\u043f\u0438\u043b\u044f\u0442\u043e\u0440 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 JIT).<\/p>\n<pre><code class=\"java\">long[256] table; long finish;  prepare(string substring) {     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (int i=0; i&lt;substring.length; i++) {         table[substring[i]] &amp;= ~(1L&lt;&lt;i); \/\/\u043d\u043e\u043b\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i     }     finish = 1&lt;&lt;(substring.length-1); } search(string input) {     long state = -1L;     for(int i=0; i&lt;input.length;i++) {         state &lt;&lt;= 1;         char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;     }     return false; }<\/code><\/pre>\n<h2>\u0420\u0430\u0441\u0448\u0438\u0440\u0435\u043d\u0438\u0435<\/h2>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c \u043e\u0431 \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u044b\u0445 \u043e\u0441\u043e\u0431\u0435\u043d\u043d\u043e\u0441\u0442\u044f\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430: \u043e\u043d \u0431\u0435\u0437 \u0438\u0437\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0432 \u043b\u043e\u0433\u0438\u043a\u0435 \u043f\u043e\u0434\u0434\u0435\u0440\u0436\u0438\u0432\u0430\u0435\u0442 \u043a\u043b\u0430\u0441\u0441\u044b \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043f\u0440\u044f\u043c\u043e \u043a\u0430\u043a \u0432 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f\u0445. \u041c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u0440\u0438 \u043f\u043e\u0434\u0433\u043e\u0442\u043e\u0432\u043a\u0435 \u0440\u0430\u0437\u0440\u0435\u0448\u0438\u0442\u044c \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0434\u043b\u044f \u043d\u0435\u0441\u043a\u043e\u043b\u044c\u043a\u0438\u0445 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u043e\u0434\u043d\u043e\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e. \u041c\u044b \u043b\u0435\u0433\u043a\u043e \u0440\u0435\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u0448\u0430\u0431\u043b\u043e\u043d\u044b \u0441 \u0443\u0441\u043b\u043e\u0432\u043d\u044b\u043c \u2018\\s\u2019 \u2014 \u043f\u0435\u0440\u0435\u0445\u043e\u0434 \u043f\u043e \u043b\u044e\u0431\u043e\u043c\u0443 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443 (\u0432 \u0442\u043e\u043c \u0447\u0438\u0441\u043b\u0435 \u0434\u043b\u044f \u043d\u0430\u0448\u0435\u0439 \u0438\u0437\u043d\u0430\u0447\u0430\u043b\u044c\u043d\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u0435\u043c \u0443\u0447\u0435\u0441\u0442\u044c \u0435\u0449\u0435 \u0438 \u0437\u043d\u0430\u043a\u0438 \u043f\u0440\u0435\u043f\u0438\u043d\u0430\u043d\u0438\u044f) \u0438 \u0434\u0430\u0436\u0435 \u2018.\u2019 \u2014 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0443 \u043f\u043e \u043b\u044e\u0431\u043e\u043c\u0443 \u0441\u0438\u043c\u0432\u043e\u043b\u0443. <\/p>\n<figure class=\"full-width\"><\/figure>\n<p>\u0421 \u043a\u043b\u0430\u0441\u0441\u0430\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0440\u0430\u0437\u043e\u0431\u0440\u0430\u043b\u0438\u0441\u044c, \u0442\u0435\u043f\u0435\u0440\u044c \u0447\u0442\u043e \u0442\u0430\u043c \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0430\u043c\u0438 \u0438\u0437 \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u044b\u0445 \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u0439? \u0414\u043b\u044f \u043f\u0440\u043e\u0441\u0442\u043e\u0442\u044b \u043f\u043e\u043f\u0440\u043e\u0431\u0443\u0435\u043c \u0432\u043d\u0435\u0434\u0440\u0438\u0442\u044c \u0432 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442 \u043f\u043e\u043d\u044f\u0442\u0438\u0435 \u2018\\s+\u2019 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u0440\u0435\u0433\u0443\u043b\u044f\u0440\u043d\u043e\u0433\u043e \u0432\u044b\u0440\u0430\u0436\u0435\u043d\u0438\u044f. \u0412\u044b\u0434\u0435\u043b\u0438\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0431\u0438\u0442 \u043f\u043e\u0434 \\s. \u0422\u0435\u043f\u0435\u0440\u044c \u0432\u043e \u0432\u0440\u0435\u043c\u044f \u0441\u0434\u0432\u0438\u0433\u0430 \u043d\u0430\u043c \u043d\u0430\u0434\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u2018\\s\u2019 \u0441\u043d\u043e\u0432\u0430 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u043c, \u0438, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u0441\u0435 \u0432 \u0431\u0438\u0442\u0430\u0445, \u043d\u0430\u043c \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0431\u0438\u0442\u043e\u0432\u0443\u044e \u043c\u0430\u0441\u043a\u0443 \u0434\u043b\u044f \u0432\u0441\u0435\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0439 \u0441 \u043f\u043b\u044e\u0441\u043e\u043c.\u00a0<\/p>\n<p>\u041d\u0430\u043b\u043e\u0436\u0438\u043c \u043c\u0430\u0441\u043a\u0443 \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0441\u043b\u043e\u0432\u043e \u0447\u0435\u0440\u0435\u0437 \u0418\u041b\u0418, \u0441\u043e\u0431\u0438\u0440\u0430\u044f \u043d\u0443\u043b\u0438 \u0432 \u0430\u043a\u0442\u0438\u0432\u043d\u044b\u0445 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f\u0445 \u043d\u0430 \u044d\u0442\u0438\u0445 \u043f\u043e\u0437\u0438\u0446\u0438\u044f\u0445, \u0441\u0434\u0432\u0438\u043d\u0435\u043c \u043d\u0430\u0437\u0430\u0434 \u0438 \u043e\u043f\u044f\u0442\u044c \u043d\u0430\u043b\u043e\u0436\u0438\u043c \u0443\u0436\u0435 \u0447\u0435\u0440\u0435\u0437 \u0418, \u0442\u0435\u043c \u0441\u0430\u043c\u044b\u043c \u0432\u043e\u0437\u0432\u0440\u0430\u0449\u0430\u044f \u0442\u043e\u043b\u044c\u043a\u043e \u044d\u0442\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043d\u0430\u0437\u0430\u0434. \u0422\u0430\u043a \u043c\u044b \u0434\u043e\u0431\u0430\u0432\u043b\u044f\u0435\u043c \u0446\u0438\u043a\u043b\u0438\u0447\u043d\u043e\u0441\u0442\u044c \u0432 \u043d\u0430\u0448 \u0430\u0432\u0442\u043e\u043c\u0430\u0442, \u043d\u0435\u043c\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0448\u0438\u0440\u0438\u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c. \u041c\u044b \u043d\u0435 \u0442\u0435\u0440\u044f\u0435\u043c \u043f\u0440\u0435\u0438\u043c\u0443\u0449\u0435\u0441\u0442\u0432 \u043d\u0430\u0448\u0435\u0433\u043e \u043f\u043e\u0431\u0438\u0442\u043e\u0432\u043e\u0433\u043e \u043f\u043e\u0434\u0445\u043e\u0434\u0430, \u043e\u0434\u043d\u0430 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f \u043e\u0431\u0441\u043b\u0443\u0436\u0438\u0432\u0430\u0435\u0442 \u0432\u0441\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c.<\/p>\n<pre><code class=\"java\">long[256] table; long finish; long plus_mask;  prepare(string pattern) {     plus_mask = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     for (int i=0; i&lt;256;i++) {         table[i] = -1L; \/\/ -1 \u044d\u0442\u043e \u0432\u0441\u0435 \u0435\u0434\u0438\u043d\u0438\u0446\u044b \u0432\u043e \u0432\u0441\u0435\u0445 \u0440\u0430\u0437\u0440\u044f\u0434\u0430\u0445     }     for (int i=0; i&lt;pattern.length; i++) {         char c = pattern[i];         long mask = (1L&lt;&lt;i); \/\/\u043d\u043e\u043b\u044c \u0432 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 i         if (isPaddingSymbol(c)) { \/\/ \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u044b\u0439 \u0441\u0438\u043c\u0432\u043e\u043b             for (p in PADDING_SYMBOLS) {                 table[p] &amp;= ~mask;             }             \/\/ \u0444\u0438\u043a\u0441\u0438\u0440\u0443\u0435\u043c 0 \u043d\u0430 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u043f\u0440\u043e\u0431\u0435\u043b\u044c\u043d\u043e\u0433\u043e \u0441\u0438\u043c\u0432\u043e\u043b\u0430             plus_mask &amp;= ~mask;           } else {             table[c] &amp;= ~mask;         }     }     finish = 1&lt;&lt;(pattern.length-1); } search(string input) {     long state = -1L;     for(int i=0; i&lt;input.length;i++) {         state &lt;&lt;= 1;         \/\/ \u0441\u0434\u0432\u0438\u0433\u0430\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043d\u0430 1 \u043d\u0430\u0437\u0430\u0434         state &amp;= (state | (plus_mask &lt;&lt; 1)) &gt;&gt; 1;          char c = input[i];         state |= table[c];         if ((state &amp; finish) == 0) return true;     }     return false; }<\/code><\/pre>\n<figure class=\"full-width\"><\/figure>\n<p>\u0421\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0441 \u043f\u043b\u044e\u0441\u043e\u043c \u043a\u0430\u0436\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u0435\u0435 \u043f\u0440\u043e\u0441\u0442\u044b\u043c, \u0447\u0435\u043c \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0441\u043e \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u043e\u0439, \u0442\u0430\u043a \u043a\u0430\u043a \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043f\u0440\u0438\u0432\u044b\u0447\u043d\u043e\u0435 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435. \u041e\u0442\u043b\u0438\u0447\u0438\u0435 \u0437\u0432\u0435\u0437\u0434\u043e\u0447\u043a\u0438 \u043b\u0438\u0448\u044c \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e \u043c\u044b \u0434\u043e\u043b\u0436\u043d\u044b \u043f\u0435\u0440\u0435\u0434\u0432\u0438\u043d\u0443\u0442\u044c \u0432\u043f\u0435\u0440\u0435\u0434 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0447\u0442\u043e\u0431\u044b \u0443\u0447\u0435\u0441\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0443\u043b\u0435\u0432\u043e\u0433\u043e \u043f\u043e\u0432\u0442\u043e\u0440\u0435\u043d\u0438\u044f. \u0422\u0430\u043a \u0447\u0442\u043e \u0434\u043b\u044f . \u043c\u044b \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0442\u043e\u0442 \u0436\u0435 \u043f\u043e\u0434\u0445\u043e\u0434, \u0442\u043e \u0435\u0441\u0442\u044c \u043c\u0430\u0441\u043a\u0430 \u0434\u043b\u044f \u043f\u043b\u044e\u0441\u0430 \u0431\u0443\u0434\u0435\u0442 \u0430\u043a\u0442\u0438\u0432\u043d\u0430 \u0438 \u0434\u043b\u044f \u044d\u0442\u043e\u0433\u043e \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f.\u00a0<\/p>\n<p>\u0422\u0435\u043f\u0435\u0440\u044c, \u0447\u0442\u043e\u0431\u044b \u043f\u0440\u0435\u0432\u0440\u0430\u0442\u0438\u0442\u044c .+ \u0432 .*, \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u043e \u0443\u0447\u0435\u0441\u0442\u044c \u0441\u043b\u0443\u0447\u0430\u0439 \u043d\u0443\u043b\u0435\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u041d\u0430 \u044f\u0437\u044b\u043a\u0435 \u0430\u0432\u0442\u043e\u043c\u0430\u0442\u043e\u0432 \u044d\u0442\u043e \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u00ab\u044d\u043f\u0441\u0438\u043b\u043e\u043d-\u043f\u0435\u0440\u0435\u0445\u043e\u0434\u00bb, \u0442\u043e \u0435\u0441\u0442\u044c \u0441\u0442\u0440\u0435\u043b\u043e\u0447\u043a\u0430, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430\u0435\u0442 \u0434\u0430\u0436\u0435 \u0431\u0435\u0437 \u0441\u0438\u043c\u0432\u043e\u043b\u0430. \u041f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0432\u0441\u0435 \u0443 \u043d\u0430\u0441 \u0432 \u0431\u0438\u0442\u043e\u0432\u043e\u043c \u043f\u043e\u0434\u0445\u043e\u0434\u0435, \u043e\u043f\u044f\u0442\u044c \u043f\u043e\u043d\u0430\u0434\u043e\u0431\u0438\u0442\u0441\u044f \u0431\u0438\u0442\u043e\u0432\u0430\u044f \u043c\u0430\u0441\u043a\u0430, \u0447\u0442\u043e\u0431\u044b \u0432\u044b\u0434\u0435\u043b\u0438\u0442\u044c \u044d\u0442\u0438 \u0441\u043e\u0441\u0442\u043e\u044f\u043d\u0438\u044f. \u0414\u0430\u043b\u044c\u0448\u0435 \u0432\u0441\u0435 \u043f\u0440\u043e\u0441\u0442\u043e: \u043f\u0440\u0438\u043c\u0435\u043d\u0438\u0432 \u043c\u0430\u0441\u043a\u0443, \u0441\u0434\u0432\u0438\u043d\u0435\u043c \u0432\u043f\u0435\u0440\u0435\u0434 \u0438 \u0441\u043d\u043e\u0432\u0430 \u043d\u0430\u043b\u043e\u0436\u0438\u043c \u043d\u0430 \u0442\u0435\u043a\u0443\u0449\u0435\u0435 \u0441\u043b\u043e\u0432\u043e.<\/p>\n<pre><code class=\"java\">long[256] table; long finish; long plus_mask; long star_mask;  prepare(string pattern) {     plus_mask = -1L; \/\/ -1<\/code><\/pre>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-459590","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/459590","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=459590"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/459590\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=459590"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=459590"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=459590"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}