{"id":443175,"date":"2024-12-26T05:53:17","date_gmt":"2024-12-26T05:53:17","guid":{"rendered":"http:\/\/savepearlharbor.com\/?p=443175"},"modified":"-0001-11-30T00:00:00","modified_gmt":"-0001-11-29T21:00:00","slug":"","status":"publish","type":"post","link":"https:\/\/savepearlharbor.com\/?p=443175","title":{"rendered":"<span>JavaScript: \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b. \u0427\u0430\u0441\u0442\u044c 7<\/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-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-src=\"https:\/\/habrastorage.org\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-blurred=\"true\"\/> <\/p>\n<p> \u041f\u0440\u0438\u0432\u0435\u0442, \u0434\u0440\u0443\u0437\u044c\u044f!<\/p>\n<p> <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432 <a href=\"https:\/\/github.com\/trekhleb\/javascript-algorithms\">\u044d\u0442\u043e\u043c \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>. \u042d\u0442\u043e \u0441\u0435\u0434\u044c\u043c\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0441\u0435\u0440\u0438\u0438.<\/p>\n<p> <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0438 \u043f\u043e\u0438\u0441\u043a\u0430.<\/p>\n<p> <\/p>\n<p>\u041a\u043e\u0434, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 \u044d\u0442\u043e\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u0441\u0435\u0440\u0438\u0438, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 <a href=\"https:\/\/github.com\/harryheman\/algorithms-data-structures\">\u044d\u0442\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>.<\/p>\n<p> <\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0448\u0443 \u043f\u043e\u0434 \u043a\u0430\u0442.<\/p>\n<p><a name=\"habracut\"><\/a> <\/p>\n<ul>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/826424\/\">\u041f\u0435\u0440\u0432\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/828068\/\">\u0412\u0442\u043e\u0440\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/832402\/\">\u0422\u0440\u0435\u0442\u044c\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/836782\/\">\u0427\u0435\u0442\u0432\u0435\u0440\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/838794\/\">\u041f\u044f\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/companies\/timeweb\/articles\/845544\/\">\u0428\u0435\u0441\u0442\u0430\u044f \u0447\u0430\u0441\u0442\u044c<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<h1 id=\"-stroki\">\u276f \u0421\u0442\u0440\u043e\u043a\u0438<\/h1>\n<p> <\/p>\n<p>\u041f\u0440\u0435\u0436\u0434\u0435 \u0447\u0435\u043c \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u0442\u044c \u043a \u0438\u0437\u0443\u0447\u0435\u043d\u0438\u044e \u043a\u043e\u043d\u043a\u0440\u0435\u0442\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432, \u0440\u0435\u043a\u043e\u043c\u0435\u043d\u0434\u0443\u044e \u0445\u043e\u0442\u044f \u0431\u044b \u0432\u043a\u0440\u0430\u0442\u0446\u0435 \u043e\u0437\u043d\u0430\u043a\u043e\u043c\u0438\u0442\u044c\u0441\u044f \u0441 \u0442\u0435\u043c, \u0447\u0442\u043e \u0442\u0430\u043a\u043e\u0435 \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435. \u0412\u043e\u0442 \u043f\u0430\u0440\u043e\u0447\u043a\u0430 \u0441\u0441\u044b\u043b\u043e\u043a:<\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B8%D0%BD%D0%B0%D0%BC%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%BE%D0%B5_%D0%BF%D1%80%D0%BE%D0%B3%D1%80%D0%B0%D0%BC%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/habr.com\/ru\/articles\/777618\/\">\u041e \u0434\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0438 \u043d\u0430 \u043f\u0430\u043b\u044c\u0446\u0430\u0445<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=U8gzm92fprI\">\u0422\u0440\u0435\u043d\u0438\u0440\u043e\u0432\u043a\u0438 \u043f\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u043e\u0442 \u042f\u043d\u0434\u0435\u043a\u0441\u0430<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<h2 id=\"-rasstoyanie-hemminga\">\u276f \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%A5%D1%8D%D0%BC%D0%BC%D0%B8%D0%BD%D0%B3%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 (\u043a\u043e\u0434\u043e\u0432\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435) (Hamming distance) \u2014 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u043f\u043e\u0437\u0438\u0446\u0438\u0439, \u0432 \u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u044e\u0449\u0438\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0434\u0432\u0443\u0445 \u0441\u0442\u0440\u043e\u043a \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0440\u0430\u0437\u043b\u0438\u0447\u043d\u044b. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u044d\u0442\u043e\u0442 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0437\u043c\u0435\u0440\u044f\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0437\u0430\u043c\u0435\u043d \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u043f\u0440\u043e\u0438\u0437\u0432\u0435\u0441\u0442\u0438 \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u0434\u0440\u0443\u0433\u0443\u044e. \u0412 \u0431\u043e\u043b\u0435\u0435 \u043e\u0431\u0449\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0441\u0442\u0440\u043e\u043a \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b \u0438 \u0441\u043b\u0443\u0436\u0438\u0442 \u043c\u0435\u0442\u0440\u0438\u043a\u043e\u0439 \u0440\u0430\u0437\u043b\u0438\u0447\u0438\u044f (\u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439, \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u044e\u0449\u0435\u0439 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0432 \u043c\u0435\u0442\u0440\u0438\u0447\u0435\u0441\u043a\u043e\u043c \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435) \u043e\u0431\u044a\u0435\u043a\u0442\u043e\u0432 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0440\u0430\u0437\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440\u044b<\/em><\/p>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 \u043c\u0435\u0436\u0434\u0443:<\/p>\n<p> <\/p>\n<ul>\n<li><code>\"karolin\"<\/code> \u0438 <code>\"kathrin\"<\/code> \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>3<\/code><\/li>\n<li><code>\"karolin\"<\/code> \u0438 <code>\"kerstin\"<\/code> \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>3<\/code><\/li>\n<li><code>1011101<\/code> \u0438 <code>1001001<\/code> \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>2<\/code><\/li>\n<li><code>2173896<\/code> \u0438 <code>2233796<\/code> \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>3<\/code><\/li>\n<\/ul>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/hamming-distance.js export default function hammingDistance(x, y) {   if (x.length !== y.length) {     throw new Error('\u0421\u0442\u0440\u043e\u043a\u0438 \u0434\u043e\u043b\u0436\u043d\u044b \u0438\u043c\u0435\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u0443\u044e \u0434\u043b\u0438\u043d\u0443')   }    let distance = 0    for (let i = 0; i &lt; x.length; i++) {     if (x[i] !== y[i]) {       distance++     }   }    return distance }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/__tests__\/hamming-distance.test.js import hammingDistance from '..\/hamming-distance'  describe('hammingDistance', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0431\u0440\u043e\u0441\u0438\u0442\u044c \u0438\u0441\u043a\u043b\u044e\u0447\u0435\u043d\u0438\u0435 \u043f\u0440\u0438 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0438 \u0441\u0442\u0440\u043e\u043a \u0440\u0430\u0437\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b', () =&gt; {     const compareStringsOfDifferentLength = () =&gt; {       hammingDistance('a', 'aa')     }      expect(compareStringsOfDifferentLength).toThrowError()   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u0425\u044d\u043c\u043c\u0438\u043d\u0433\u0430 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438', () =&gt; {     expect(hammingDistance('a', 'a')).toBe(0)     expect(hammingDistance('a', 'b')).toBe(1)     expect(hammingDistance('abc', 'add')).toBe(2)     expect(hammingDistance('karolin', 'kathrin')).toBe(3)     expect(hammingDistance('karolin', 'kerstin')).toBe(3)     expect(hammingDistance('1011101', '1001001')).toBe(2)     expect(hammingDistance('2173896', '2233796')).toBe(3)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/strings\/__tests__\/hamming-distance<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/_m\/xt\/4d\/_mxt4dl8i08uve8frcoerxzyzq4.png\" data-src=\"https:\/\/habrastorage.org\/webt\/_m\/xt\/4d\/_mxt4dl8i08uve8frcoerxzyzq4.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-rasstoyanie-levenshteyna\">\u276f \u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%A0%D0%B0%D1%81%D1%81%D1%82%D0%BE%D1%8F%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B5%D0%B2%D0%B5%D0%BD%D1%88%D1%82%D0%B5%D0%B9%D0%BD%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=We3YDTzNXEk\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 (\u0440\u0435\u0434\u0430\u043a\u0446\u0438\u043e\u043d\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435, \u0434\u0438\u0441\u0442\u0430\u043d\u0446\u0438\u044f \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f) (Levenshtein distance) \u2014 \u044d\u0442\u043e \u043c\u0435\u0442\u0440\u0438\u043a\u0430, \u0438\u0437\u043c\u0435\u0440\u044f\u044e\u0449\u0430\u044f \u043f\u043e \u043c\u043e\u0434\u0443\u043b\u044e \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u044c \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044f\u043c\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432. \u041e\u043d\u0430 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u043a\u0430\u043a \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u0434\u043d\u043e\u0441\u0438\u043c\u0432\u043e\u043b\u044c\u043d\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 (\u0432\u0441\u0442\u0430\u0432\u043a\u0438, \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044f \u0438\u043b\u0438 \u0437\u0430\u043c\u0435\u043d\u044b), \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u0434\u043b\u044f \u043f\u0440\u0435\u0432\u0440\u0430\u0449\u0435\u043d\u0438\u044f \u043e\u0434\u043d\u043e\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432 \u0432 \u0434\u0440\u0443\u0433\u0443\u044e.<\/p>\n<p> <\/p>\n<p><em>\u041e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p>\u041c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u0438, \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 <code>a<\/code> \u0438 <code>b<\/code> (\u0434\u043b\u0438\u043d\u043e\u0439 <code>|a|<\/code> \u0438 <code>|b|<\/code>, \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0435\u043d\u043d\u043e) \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442\u0441\u044f \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/u8\/pw\/cj\/u8pwcj8plkugg65mltdbx2probi.png\" data-src=\"https:\/\/habrastorage.org\/webt\/u8\/pw\/cj\/u8pwcj8plkugg65mltdbx2probi.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0433\u0434\u0435<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/f4\/ma\/1s\/f4ma1soichcqqwi2sacpbddrppm.png\" data-src=\"https:\/\/habrastorage.org\/webt\/f4\/ma\/1s\/f4ma1soichcqqwi2sacpbddrppm.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0417\u0434\u0435\u0441\u044c<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/lz\/hp\/mv\/lzhpmvu2npuevit96dmej1hfw6w.png\" data-src=\"https:\/\/habrastorage.org\/webt\/lz\/hp\/mv\/lzhpmvu2npuevit96dmej1hfw6w.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u044d\u0442\u043e \u0438\u043d\u0434\u0438\u043a\u0430\u0442\u043e\u0440\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f (indicator function), \u0440\u0430\u0432\u043d\u0430\u044f <code>0<\/code>, \u043a\u043e\u0433\u0434\u0430<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/5f\/re\/nx\/5frenxzbiyoly4epojsyk9zqd8c.png\" data-src=\"https:\/\/habrastorage.org\/webt\/5f\/re\/nx\/5frenxzbiyoly4epojsyk9zqd8c.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0438 <code>1<\/code>, \u0432 \u043f\u0440\u043e\u0442\u0438\u0432\u043d\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435, \u0430<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/l2\/y4\/qd\/l2y4qdgzhvycl6rhf8njw34c_wa.png\" data-src=\"https:\/\/habrastorage.org\/webt\/l2\/y4\/qd\/l2y4qdgzhvycl6rhf8njw34c_wa.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u044d\u0442\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u043c\u0435\u0436\u0434\u0443 \u043f\u0435\u0440\u0432\u044b\u043c\u0438 <code>i<\/code> \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438 <code>a<\/code> \u0438 \u043f\u0435\u0440\u0432\u044b\u043c\u0438 <code>j<\/code> \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438 <code>b<\/code>.<\/p>\n<p> <\/p>\n<p>\u041e\u0431\u0440\u0430\u0442\u0438\u0442\u0435 \u0432\u043d\u0438\u043c\u0430\u043d\u0438\u0435, \u0447\u0442\u043e \u043f\u0435\u0440\u0432\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 <code>min<\/code> \u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0443\u0435\u0442 \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u044e, \u0432\u0442\u043e\u0440\u043e\u0439 \u2014 \u0432\u0441\u0442\u0430\u0432\u043a\u0435, \u0442\u0440\u0435\u0442\u0438\u0439 \u2014 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044e \u0438\u043b\u0438 \u043d\u0435\u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044e \u0432 \u0437\u0430\u0432\u0438\u0441\u0438\u043c\u043e\u0441\u0442\u0438 \u043e\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0441\u0442\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440<\/em><\/p>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u043c\u0435\u0436\u0434\u0443 <code>kitten<\/code> \u0438 <code>sitting<\/code> \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f <code>3<\/code>, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432\u043e \u0432\u0442\u043e\u0440\u0443\u044e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u043e \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u0435 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438:<\/p>\n<p> <\/p>\n<ul>\n<li>kitten -&gt; sitten (\u0437\u0430\u043c\u0435\u043d\u0430 <code>k<\/code> \u043d\u0430 <code>s<\/code>)<\/li>\n<li>sitten -&gt; sittin (\u0437\u0430\u043c\u0435\u043d\u0430 <code>e<\/code> \u043d\u0430 <code>i<\/code>)<\/li>\n<li>sittin -&gt; sitting (\u0432\u0441\u0442\u0430\u0432\u043a\u0430 <code>g<\/code> \u0432 \u043a\u043e\u043d\u0435\u0446)<\/li>\n<\/ul>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0432 \u0431\u043e\u043b\u044c\u0448\u043e\u043c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0435 \u043f\u0440\u0438\u043b\u043e\u0436\u0435\u043d\u0438\u0439, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0441\u0440\u0435\u0434\u0441\u0442\u0432\u0430\u0445 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u043e\u0440\u0444\u043e\u0433\u0440\u0430\u0444\u0438\u0438, \u0441\u0438\u0441\u0442\u0435\u043c\u0430\u0445 \u0438\u0441\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u043e\u043f\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0433\u043e \u0440\u0430\u0441\u043f\u043e\u0437\u043d\u0430\u0432\u0430\u043d\u0438\u044f \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432, \u043d\u0435\u0442\u043e\u0447\u043d\u043e\u0433\u043e (fuzzy) \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0442\u0440\u043e\u043a \u0438 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u043d\u043e\u043c \u043e\u0431\u0435\u0441\u043f\u0435\u0447\u0435\u043d\u0438\u0438 \u0434\u043b\u044f \u043e\u0431\u043b\u0435\u0433\u0447\u0435\u043d\u0438\u044f \u043f\u0435\u0440\u0435\u0432\u043e\u0434\u0430 \u043d\u0430 \u0435\u0441\u0442\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0439 \u044f\u0437\u044b\u043a.<\/p>\n<p> <\/p>\n<p><em>\u0414\u0438\u043d\u0430\u043c\u0438\u0447\u0435\u0441\u043a\u043e\u0435 \u043f\u0440\u043e\u0433\u0440\u0430\u043c\u043c\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p>\u0420\u0430\u0441\u0441\u043c\u043e\u0442\u0440\u0438\u043c \u043f\u0440\u043e\u0441\u0442\u043e\u0439 \u043f\u0440\u0438\u043c\u0435\u0440 \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u0440\u0435\u0434\u0430\u043a\u0446\u0438\u043e\u043d\u043d\u043e\u0433\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u043c\u0435\u0436\u0434\u0443 \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 <code>ME<\/code> \u0438 <code>MY<\/code>. \u0418\u043d\u0442\u0443\u0438\u0442\u0438\u0432\u043d\u043e \u043c\u044b \u043f\u043e\u043d\u0438\u043c\u0430\u0435\u043c, \u0447\u0442\u043e \u043e\u043d\u043e \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f <code>1<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438, \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0437\u0430\u043c\u0435\u043d\u0430 <code>E<\/code> \u043d\u0430 <code>Y<\/code>. \u041e\u0434\u043d\u0430\u043a\u043e \u0434\u0430\u0432\u0430\u0439\u0442\u0435 \u0444\u043e\u0440\u043c\u0430\u043b\u0438\u0437\u0443\u0435\u043c \u044d\u0442\u043e \u0432 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u0447\u0442\u043e\u0431\u044b \u0438\u043c\u0435\u0442\u044c \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e\u0441\u0442\u044c \u0440\u0435\u0448\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0437\u0430\u0434\u0430\u0447\u0443 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>Saturday<\/code> \u0432 <code>Sunday<\/code>.<\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u044f \u0443\u043a\u0430\u0437\u0430\u043d\u043d\u043e\u0439 \u0432\u044b\u0448\u0435 \u043c\u0430\u0442\u0435\u043c\u0430\u0442\u0438\u0447\u0435\u0441\u043a\u043e\u0439 \u0444\u043e\u0440\u043c\u0443\u043b\u044b \u043a \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044e <code>ME -&gt; MY<\/code> \u043d\u0430\u043c \u0434\u043b\u044f \u043d\u0430\u0447\u0430\u043b\u0430 \u043d\u0443\u0436\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f <code>ME -&gt; M<\/code>, <code>M -&gt; MY<\/code> \u0438 <code>M -&gt; M<\/code>. \u0417\u0430\u0442\u0435\u043c \u043d\u0430\u0434\u043e \u0432\u0437\u044f\u0442\u044c \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c \u043e\u0434\u043d\u0443 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044e \u0434\u043b\u044f \u0437\u0430\u043c\u0435\u043d\u044b <code>E<\/code> \u043d\u0430 <code>Y<\/code>. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0435 \u0440\u0435\u0434\u0430\u043a\u0446\u0438\u043e\u043d\u043d\u043e\u0435 \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u0435 \u0442\u0440\u0430\u043d\u0441\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438 <code>ME -&gt; MY<\/code> \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u0442\u0440\u0435\u0445 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445 \u0432\u043e\u0437\u043c\u043e\u0436\u043d\u044b\u0445 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0439.<\/p>\n<p> <\/p>\n<p>\u041d\u0430\u0440\u0438\u0441\u0443\u0435\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u0443:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/ql\/la\/l6\/qllal6twrhbs-dtnfeuzrwrbzia.png\" data-src=\"https:\/\/habrastorage.org\/webt\/ql\/la\/l6\/qllal6twrhbs-dtnfeuzrwrbzia.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<ul>\n<li>\u042f\u0447\u0435\u0439\u043a\u0430 <code>(0:1)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043a\u0440\u0430\u0441\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>1<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>M<\/code> \u0432 \u043f\u0443\u0441\u0442\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>1<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f. \u042d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435. \u0412\u043e\u0442 \u043f\u043e\u0447\u0435\u043c\u0443 \u0447\u0438\u0441\u043b\u043e \u043a\u0440\u0430\u0441\u043d\u043e\u0435<\/li>\n<li>\u044f\u0447\u0435\u0439\u043a\u0430 <code>(0:2)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043a\u0440\u0430\u0441\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>2<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>ME<\/code> \u0432 \u043f\u0443\u0441\u0442\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>2<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438. \u042d\u0442\u0438\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 <code>E<\/code> \u0438 <code>M<\/code><\/li>\n<li>\u044f\u0447\u0435\u0439\u043a\u0430 <code>(1:0)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0437\u0435\u043b\u0435\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>1<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0443\u0441\u0442\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432 <code>M<\/code> \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>1<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f. \u042d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0430 <code>M<\/code>. \u0412\u043e\u0442 \u043f\u043e\u0447\u0435\u043c\u0443 \u0447\u0438\u0441\u043b\u043e \u0437\u0435\u043b\u0435\u043d\u043e\u0435<\/li>\n<li>\u044f\u0447\u0435\u0439\u043a\u0430 <code>(2:0)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0437\u0435\u043b\u0435\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>2<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f \u043f\u0443\u0441\u0442\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438 \u0432 <code>MY<\/code> \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>2<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0438. \u042d\u0442\u0438\u043c\u0438 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f \u0432\u0441\u0442\u0430\u0432\u043a\u0430 <code>Y<\/code> \u0438 <code>M<\/code><\/li>\n<li>\u044f\u0447\u0435\u0439\u043a\u0430 <code>(1:1)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0447\u0438\u0441\u043b\u043e <code>0<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>M<\/code> \u0432 <code>M<\/code> \u043d\u0438\u0447\u0435\u0433\u043e \u0434\u0435\u043b\u0430\u0442\u044c \u043d\u0435 \u043d\u0443\u0436\u043d\u043e<\/li>\n<li>\u044f\u0447\u0435\u0439\u043a\u0430 <code>(1:2)<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u043a\u0440\u0430\u0441\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e <code>1<\/code>. \u042d\u0442\u043e \u043e\u0437\u043d\u0430\u0447\u0430\u0435\u0442, \u0447\u0442\u043e \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>ME<\/code> \u0432 <code>M<\/code> \u0442\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f <code>1<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u044f. \u042d\u0442\u043e\u0439 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435 <code>E<\/code><\/li>\n<li>\u0438 \u0442.\u0434.<\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u043d\u0435\u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 (\u0432 \u043d\u0430\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 <code>3x3<\/code>) \u0432\u0441\u0435 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442 \u043f\u0440\u043e\u0441\u0442\u043e, \u043d\u043e \u0442\u043e\u0436\u0435 \u0441\u0430\u043c\u043e\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0442\u0430\u043a\u0438\u0445 \u0447\u0438\u0441\u0435\u043b \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043c\u0430\u0442\u0440\u0438\u0446 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, <code>9x7<\/code> \u0434\u043b\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u044f <code>Saturday -&gt; Sunday<\/code>).<\/p>\n<p> <\/p>\n<p>\u0421\u043e\u0433\u043b\u0430\u0441\u043d\u043e \u0444\u043e\u0440\u043c\u0443\u043b\u0435 \u043d\u0430\u043c \u043d\u0443\u0436\u043d\u044b 3 \u0441\u043e\u0441\u0435\u0434\u043d\u0438\u0435 \u044f\u0447\u0435\u0439\u043a\u0438 <code>(i-1:j)<\/code>, <code>(i-1:j-1)<\/code> \u0438 <code>(i:j-1)<\/code> \u0434\u043b\u044f \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044f \u0447\u0438\u0441\u043b\u0430 \u0434\u043b\u044f \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u044f\u0447\u0435\u0439\u043a\u0438 <code>(i:j)<\/code>. \u0412\u0441\u0435, \u0447\u0442\u043e \u043d\u0443\u0436\u043d\u043e \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u2014 \u043d\u0430\u0439\u0442\u0438 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0441\u043e\u0441\u0435\u0434\u043d\u044e\u044e \u044f\u0447\u0435\u0439\u043a\u0443 \u0438 \u043f\u0440\u0438\u0431\u0430\u0432\u0438\u0442\u044c \u043a \u043d\u0435\u0439 <code>1<\/code> \u0432 \u0441\u043b\u0443\u0447\u0430\u0435, \u0435\u0441\u043b\u0438 \u0441\u0442\u0440\u043e\u043a\u0430 <code>i<\/code> \u0438 \u043a\u043e\u043b\u043e\u043d\u043a\u0430 <code>j<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0430\u0442 \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0438\u043c\u0432\u043e\u043b\u044b.<\/p>\n<p> <\/p>\n<p>\u0420\u0435\u043a\u0443\u0440\u0441\u0438\u0432\u043d\u0443\u044e \u043f\u0440\u0438\u0440\u043e\u0434\u0443 \u0437\u0430\u0434\u0430\u0447\u0438 \u043c\u043e\u0436\u043d\u043e \u043f\u0440\u043e\u0438\u043b\u043b\u044e\u0441\u0442\u0440\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/k4\/hk\/6g\/k4hk6ggffvenk3yutoqhaswouou.png\" data-src=\"https:\/\/habrastorage.org\/webt\/k4\/hk\/6g\/k4hk6ggffvenk3yutoqhaswouou.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041d\u0430\u0440\u0438\u0441\u0443\u0435\u043c \u0433\u0440\u0430\u0444 \u0440\u0435\u0448\u0435\u043d\u0438\u0439 \u0434\u043b\u044f \u044d\u0442\u043e\u0439 \u0437\u0430\u0434\u0430\u0447\u0438:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/c0\/iw\/y-\/c0iwy-avihbyx5azctewwuuvzqi.png\" data-src=\"https:\/\/habrastorage.org\/webt\/c0\/iw\/y-\/c0iwy-avihbyx5azctewwuuvzqi.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0412\u044b \u043c\u043e\u0436\u0435\u0442\u0435 \u0432\u0438\u0434\u0435\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043f\u0435\u0440\u0435\u043a\u0440\u044b\u0432\u0430\u044e\u0449\u0438\u0445\u0441\u044f \u0437\u0430\u0434\u0430\u0447, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043f\u043e\u043c\u0435\u0447\u0435\u043d\u044b \u0436\u0435\u043b\u0442\u044b\u043c. \u041d\u0435 \u0441\u0443\u0449\u0435\u0441\u0442\u0432\u0443\u0435\u0442 \u0441\u043f\u043e\u0441\u043e\u0431\u0430 \u0443\u043c\u0435\u043d\u044c\u0448\u0438\u0442\u044c \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0438 \u0441\u0434\u0435\u043b\u0430\u0442\u044c \u0435\u0433\u043e \u043c\u0435\u043d\u044c\u0448\u0435 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u043e\u0439 \u0438\u0437 \u044d\u0442\u0438\u0445 \u0442\u0440\u0435\u0445 \u044f\u0447\u0435\u0435\u043a.<\/p>\n<p> <\/p>\n<p>\u0422\u0430\u043a\u0436\u0435 \u043c\u043e\u0436\u043d\u043e \u0432\u0438\u0434\u0435\u0442\u044c, \u0447\u0442\u043e \u043a\u0430\u0436\u0434\u043e\u0435 \u0447\u0438\u0441\u043b\u043e \u044f\u0447\u0435\u0439\u043a\u0438 \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442\u0441\u044f \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0438\u0445. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0434\u0435\u0441\u044c \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u0442\u0441\u044f \u0442\u0435\u0445\u043d\u0438\u043a\u0430 \u0442\u0430\u0431\u0443\u043b\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f (\u0437\u0430\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u0435 \u043a\u044d\u0448\u0430 \u0441\u043d\u0438\u0437\u0443 \u0432\u0432\u0435\u0440\u0445).<\/p>\n<p> <\/p>\n<p>\u0414\u0430\u043b\u044c\u043d\u0435\u0439\u0448\u0435\u0435 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435 \u044d\u0442\u043e\u0433\u043e \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0430 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0440\u0435\u0448\u0430\u0442\u044c \u0431\u043e\u043b\u0435\u0435 \u0441\u043b\u043e\u0436\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u043e\u0432\u0430\u043d\u0438\u0435 <code>Saturday -&gt; Sunday<\/code>:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/e3\/gb\/xf\/e3gbxfafyhyv4xqea6yrrvfr5lc.png\" data-src=\"https:\/\/habrastorage.org\/webt\/e3\/gb\/xf\/e3gbxfafyhyv4xqea6yrrvfr5lc.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/levenshtein-distance.js export default function levenshteinDistance(a, b) {   \/\/ \u0421\u043e\u0437\u0434\u0430\u0435\u043c \u043f\u0443\u0441\u0442\u0443\u044e \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f   const matrix = new Array(b.length + 1)     .fill(null)     .map(() =&gt; new Array(a.length + 1).fill(null))    \/\/ \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u043c\u0430\u0442\u0440\u0438\u0446\u044b.   \/\/ \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043f\u0435\u0440\u0432\u0430\u044f \u0441\u0442\u0440\u043e\u043a\u0430, \u0442\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c \u043f\u0443\u0441\u0442\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0432 `a`.   \/\/ \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0439 \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438   for (let i = 0; i &lt;= a.length; i++) {     matrix[0][i] = i   }    \/\/ \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u043a\u043e\u043b\u043e\u043d\u043a\u0443 \u043c\u0430\u0442\u0440\u0438\u0446\u044b.   \/\/ \u0415\u0441\u043b\u0438 \u044d\u0442\u043e \u043f\u0435\u0440\u0432\u0430\u044f \u043a\u043e\u043b\u043e\u043d\u043a\u0430, \u0442\u043e\u0433\u0434\u0430 \u043c\u044b \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u043c \u043f\u0443\u0441\u0442\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0432 `b`.   \/\/ \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u043c\u043e\u0434\u0438\u0444\u0438\u043a\u0430\u0446\u0438\u0439 \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f \u0440\u0430\u0437\u043c\u0435\u0440\u0443 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438   for (let j = 0; j &lt;= b.length; j++) {     matrix[j][0] = j   }    \/\/ \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043c\u0430\u0442\u0440\u0438\u0446\u0443 \u0440\u0435\u0434\u0430\u043a\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f   for (let j = 1; j &lt;= b.length; j++) {     for (let i = 1; i &lt;= a.length; i++) {       const indicator = b[j - 1] === a[i - 1] ? 0 : 1       matrix[j][i] = Math.min(         matrix[j][i - 1] + 1, \/\/ \u0443\u0434\u0430\u043b\u0435\u043d\u0438\u0435         matrix[j - 1][i] + 1, \/\/ \u0432\u0441\u0442\u0430\u0432\u043a\u0430         matrix[j - 1][i - 1] + indicator, \/\/ \u0437\u0430\u043c\u0435\u043d\u0430       )     }   }    return matrix[b.length][a.length] }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/__tests__\/levenshtein-distance.test.js import levenshteinDistance from '..\/levenshtein-distance'  describe('levenshteinDistance', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u0432\u044b\u0447\u0438\u0441\u043b\u0438\u0442\u044c \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044f \u041b\u0435\u0432\u0435\u043d\u0448\u0442\u0435\u0439\u043d\u0430 \u043c\u0435\u0436\u0434\u0443 \u0434\u0432\u0443\u043c\u044f \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438', () =&gt; {     expect(levenshteinDistance('', '')).toBe(0)     expect(levenshteinDistance('a', '')).toBe(1)     expect(levenshteinDistance('', 'a')).toBe(1)     expect(levenshteinDistance('abc', '')).toBe(3)     expect(levenshteinDistance('', 'abc')).toBe(3)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c `I` \u0432 \u043d\u0430\u0447\u0430\u043b\u043e     expect(levenshteinDistance('islander', 'slander')).toBe(1)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c `M` \u043d\u0430 `K`, `T` \u043d\u0430 `M` \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c `A` \u0432 \u043a\u043e\u043d\u0435\u0446     expect(levenshteinDistance('mart', 'karma')).toBe(3)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c `K` \u043d\u0430 `S`, `E` \u043d\u0430 `I` \u0438 \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c `G` \u0432 \u043a\u043e\u043d\u0435\u0446     expect(levenshteinDistance('kitten', 'sitting')).toBe(3)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0434\u043e\u0431\u0430\u0432\u0438\u0442\u044c 4 \u0431\u0443\u043a\u0432\u044b `FOOT` \u0432 \u043d\u0430\u0447\u0430\u043b\u043e     expect(levenshteinDistance('ball', 'football')).toBe(4)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0443\u0434\u0430\u043b\u0438\u0442\u044c 4 \u0431\u0443\u043a\u0432\u044b `FOOT` \u0432 \u043d\u0430\u0447\u0430\u043b\u0435     expect(levenshteinDistance('football', 'foot')).toBe(4)      \/\/ \u041d\u0443\u0436\u043d\u043e \u0437\u0430\u043c\u0435\u043d\u0438\u0442\u044c \u043f\u0435\u0440\u0432\u044b\u0435 5 \u0431\u0443\u043a\u0432 `INTEN` \u043d\u0430 `EXECU`     expect(levenshteinDistance('intention', 'execution')).toBe(5)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/strings\/__tests__\/levenshtein-distance<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/ls\/g-\/fc\/lsg-fcgmrcptnrnorutupag_zxo.png\" data-src=\"https:\/\/habrastorage.org\/webt\/ls\/g-\/fc\/lsg-fcgmrcptnrnorutupag_zxo.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-algoritm-knuta-morrisa-pratta\">\u276f \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041a\u043d\u0443\u0442\u0430-\u041c\u043e\u0440\u0440\u0438\u0441\u0430-\u041f\u0440\u0430\u0442\u0442\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%BD%D1%83%D1%82%D0%B0_%E2%80%94_%D0%9C%D0%BE%D1%80%D1%80%D0%B8%D1%81%D0%B0_%E2%80%94_%D0%9F%D1%80%D0%B0%D1%82%D1%82%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=7g-WEBj3igk\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u041a\u043d\u0443\u0442\u0430-\u041c\u043e\u0440\u0440\u0438\u0441\u0430-\u041f\u0440\u0430\u0442\u0442\u0430 (\u041a\u041c\u041f-\u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c) (Knuth\u2013Morris\u2013Pratt algorithm) \u2014 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c, \u043e\u0441\u0443\u0449\u0435\u0441\u0442\u0432\u043b\u044f\u044e\u0449\u0438\u0439 \u043f\u043e\u0438\u0441\u043a \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0442\u043e, \u0447\u0442\u043e \u043f\u0440\u0438 \u0432\u043e\u0437\u043d\u0438\u043a\u043d\u043e\u0432\u0435\u043d\u0438\u0438 \u043d\u0435\u0441\u043e\u043e\u0442\u0432\u0435\u0442\u0441\u0442\u0432\u0438\u044f \u0441\u0430\u043c\u043e \u0441\u043b\u043e\u0432\u043e \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442 \u0434\u043e\u0441\u0442\u0430\u0442\u043e\u0447\u043d\u043e \u0438\u043d\u0444\u043e\u0440\u043c\u0430\u0446\u0438\u0438, \u0447\u0442\u043e\u0431\u044b \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c, \u0433\u0434\u0435 \u043c\u043e\u0436\u0435\u0442 \u043d\u0430\u0447\u0430\u0442\u044c\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u043c\u0438\u043d\u0443\u044f \u043b\u0438\u0448\u043d\u0438\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438. \u0412\u0440\u0435\u043c\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u043e\u0431\u044a\u0435\u043c\u0430 \u0432\u0445\u043e\u0434\u043d\u044b\u0445 \u0434\u0430\u043d\u043d\u044b\u0445, \u0442\u043e \u0435\u0441\u0442\u044c \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0430\u0441\u0438\u043c\u043f\u0442\u043e\u0442\u0438\u0447\u0435\u0441\u043a\u0438 \u0431\u043e\u043b\u0435\u0435 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043d\u0435\u0432\u043e\u0437\u043c\u043e\u0436\u043d\u043e.<\/p>\n<p> <\/p>\n<p><em>\u0417\u0430\u0434\u0430\u0447\u0430<\/em><\/p>\n<p> <\/p>\n<p>\u0414\u0430\u043d\u044b \u043e\u0431\u0440\u0430\u0437\u0435\u0446 (\u0441\u0442\u0440\u043e\u043a\u0430) <code>S<\/code> \u0438 \u0441\u0442\u0440\u043e\u043a\u0430 <code>T<\/code>. \u0422\u0440\u0435\u0431\u0443\u0435\u0442\u0441\u044f \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0438\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u043a\u043e\u0442\u043e\u0440\u043e\u0433\u043e \u043e\u0431\u0440\u0430\u0437\u0435\u0446 <code>S<\/code> \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 <code>T<\/code>. \u0415\u0441\u043b\u0438 <code>S<\/code> \u043d\u0435 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442\u0441\u044f \u0432 <code>T<\/code>, \u043d\u0443\u0436\u043d\u043e \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0438\u043d\u0434\u0435\u043a\u0441, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u043d\u0435 \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0442\u044c \u0438\u043d\u0442\u0435\u0440\u043f\u0440\u0435\u0442\u0438\u0440\u043e\u0432\u0430\u043d \u043a\u0430\u043a \u043f\u043e\u0437\u0438\u0446\u0438\u044f \u0432 \u0441\u0442\u0440\u043e\u043a\u0435 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043e\u0442\u0440\u0438\u0446\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e).<\/p>\n<p> <\/p>\n<p><em>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em><\/p>\n<p> <\/p>\n<ul>\n<li>\u0412\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f: <code>O(|W| + |T|)<\/code> (\u0447\u0442\u043e \u0433\u043e\u0440\u0430\u0437\u0434\u043e \u0431\u044b\u0441\u0442\u0440\u0435\u0435 \u0442\u0440\u0438\u0432\u0438\u0430\u043b\u044c\u043d\u043e\u0433\u043e <code>O(|W| * |T|)<\/code>)<\/li>\n<li>\u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435\u043d\u043d\u0430\u044f: <code>O(|W|)<\/code><\/li>\n<\/ul>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u041d\u0430\u0447\u043d\u0435\u043c \u0441 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u0432\u0440\u0435\u043c\u0435\u043d\u043d\u043e\u0439 \u0442\u0430\u0431\u043b\u0438\u0446\u044b \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/knuth-morris-pratt.js function buildPatternTable(word) {   const patternTable = [0]   let prefixIndex = 0   let suffixIndex = 1    while (suffixIndex &lt; word.length) {     if (word[suffixIndex] === word[prefixIndex]) {       patternTable[suffixIndex] = prefixIndex + 1       prefixIndex += 1       suffixIndex += 1     } else if (prefixIndex === 0) {       patternTable[suffixIndex] = 0       suffixIndex += 1     } else {       prefixIndex = patternTable[prefixIndex - 1]     }   }    return patternTable }<\/code><\/pre>\n<p> <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u044d\u0442\u0443 \u0442\u0430\u0431\u043b\u0438\u0446\u0443 \u0434\u043b\u044f \u0440\u0435\u0448\u0435\u043d\u0438\u044f \u0437\u0430\u0434\u0430\u0447\u0438:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">export default function knuthMorrisPratt(text, word) {   if (word.length === 0) return 0    let textIndex = 0   let wordIndex = 0    const patternTable = buildPatternTable(word)    while (textIndex &lt; text.length) {     if (text[textIndex] === word[wordIndex]) {       \/\/ \u041d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435       if (wordIndex === word.length - 1) {         return textIndex - word.length + 1       }        textIndex += 1       wordIndex += 1     } else if (wordIndex &gt; 0) {       wordIndex = patternTable[wordIndex - 1]     } else {       textIndex += 1     }   }    return -1 }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/__tests__\/knuth-morris-pratt.test.js import knuthMorrisPratt from '..\/knuth-morris-pratt'  describe('knuthMorrisPratt', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0435 \u0438\u043d\u0434\u0435\u043a\u0441\u044b \u0441\u043b\u043e\u0432 \u0432 \u0442\u0435\u043a\u0441\u0442\u0430\u0445', () =&gt; {     expect(knuthMorrisPratt('', '')).toBe(0)     expect(knuthMorrisPratt('a', '')).toBe(0)     expect(knuthMorrisPratt('a', 'a')).toBe(0)     expect(knuthMorrisPratt('abcbcglx', 'abca')).toBe(-1)     expect(knuthMorrisPratt('abcbcglx', 'bcgl')).toBe(3)     expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15)     expect(knuthMorrisPratt('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1)     expect(       knuthMorrisPratt('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca'),     ).toBe(12)     expect(       knuthMorrisPratt('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa'),     ).toBe(11)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/strings\/__tests__\/knuth-morris-pratt<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/o2\/ld\/li\/o2ldliucllzvmnitwspzbjxmzwo.png\" data-src=\"https:\/\/habrastorage.org\/webt\/o2\/ld\/li\/o2ldliucllzvmnitwspzbjxmzwo.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-algoritm-rabina-karpa\">\u276f \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0420\u0430\u0431\u0438\u043d\u0430-\u041a\u0430\u0440\u043f\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A0%D0%B0%D0%B1%D0%B8%D0%BD%D0%B0_%E2%80%94_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=H4VrKHVG5qI\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0420\u0430\u0431\u0438\u043d\u0430-\u041a\u0430\u0440\u043f\u0430 (Rabin-Karp Algorithm) \u2014 \u044d\u0442\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u0441\u0442\u0440\u043e\u043a\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0438\u0449\u0435\u0442 \u0448\u0430\u0431\u043b\u043e\u043d, \u0442\u043e \u0435\u0441\u0442\u044c \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443, \u0432 \u0442\u0435\u043a\u0441\u0442\u0435, \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435.<\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=xV8USnjKGCU\">\u041e\u0442\u043b\u0438\u0447\u043d\u043e\u0435 \u0432\u0438\u0434\u0435\u043e \u043f\u0440\u043e \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0440\u0435\u0434\u043a\u043e \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u043e\u0434\u0438\u043d\u043e\u0447\u043d\u043e\u0433\u043e \u0448\u0430\u0431\u043b\u043e\u043d\u0430, \u043d\u043e \u0438\u043c\u0435\u0435\u0442 \u0437\u043d\u0430\u0447\u0438\u0442\u0435\u043b\u044c\u043d\u0443\u044e \u0442\u0435\u043e\u0440\u0435\u0442\u0438\u0447\u0435\u0441\u043a\u0443\u044e \u0432\u0430\u0436\u043d\u043e\u0441\u0442\u044c \u0438 \u043e\u0447\u0435\u043d\u044c \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u0435\u043d \u0432 \u043f\u043e\u0438\u0441\u043a\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0439 \u043c\u043d\u043e\u0436\u0435\u0441\u0442\u0432\u0435\u043d\u043d\u044b\u0445 \u0448\u0430\u0431\u043b\u043e\u043d\u043e\u0432 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u043e\u0439 \u0434\u043b\u0438\u043d\u044b. \u0425\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f \u2014 \u044d\u0442\u043e \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u043a\u0430\u0436\u0434\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0432 \u0447\u0438\u0441\u043b\u043e\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u043d\u0430\u0437\u044b\u0432\u0430\u0435\u0442\u0441\u044f \u0445\u044d\u0448\u0435\u043c. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043c\u044b \u043c\u043e\u0436\u0435\u043c \u043f\u043e\u043b\u0443\u0447\u0438\u0442\u044c <code>hash('hello') = 5<\/code>. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u0438\u0437 \u043f\u0440\u0435\u0434\u043f\u043e\u043b\u043e\u0436\u0435\u043d\u0438\u044f, \u0447\u0442\u043e \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u0441\u0442\u0440\u043e\u043a\u0438 \u0438\u043c\u0435\u044e\u0442 \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0439 \u0445\u044d\u0448. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0437\u0430\u0434\u0430\u0447\u0430 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0441\u0432\u043e\u0434\u0438\u0442\u0441\u044f \u043a \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u044e \u0445\u044d\u0448\u0430 \u0438\u0441\u043a\u043e\u043c\u043e\u0433\u043e \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430 \u0438 \u043f\u043e\u0438\u0441\u043a \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0432\u0445\u043e\u0434\u043d\u043e\u0439 \u0441\u0442\u0440\u043e\u043a\u0438, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u0438\u043c\u0435\u044e\u0442 \u0442\u0430\u043a\u043e\u0439 \u0436\u0435 \u0445\u044d\u0448.<\/p>\n<p> <\/p>\n<p>\u041e\u0434\u043d\u0430\u043a\u043e \u0443 \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u0435\u043c\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0435\u0441\u0442\u044c \u0434\u0432\u0435 \u043f\u0440\u043e\u0431\u043b\u0435\u043c\u044b. \u0412\u043e-\u043f\u0435\u0440\u0432\u044b\u0445, \u0441\u0442\u0440\u043e\u043a \u043c\u043d\u043e\u0433\u043e, \u0430 \u0445\u044d\u0448\u0435\u0439 \u043c\u0430\u043b\u043e, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0440\u0430\u0437\u043d\u044b\u0435 \u0441\u0442\u0440\u043e\u043a\u0438 \u043c\u043e\u0433\u0443\u0442 \u0438\u043c\u0435\u0442\u044c \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0439 \u0445\u044d\u0448. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u043f\u0440\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u0445\u044d\u0448\u0435\u0439 \u043f\u0430\u0442\u0442\u0435\u0440\u043d \u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043c\u043e\u0433\u0443\u0442 \u043d\u0435 \u0441\u043e\u0432\u043f\u0430\u0434\u0430\u0442\u044c. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u0430 \u0441 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u043e\u0439 \u0434\u043e\u043b\u0436\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0442\u044c\u0441\u044f \u043f\u0443\u0442\u0435\u043c \u0438\u0445 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f. \u0422\u0430\u043a\u043e\u0435 \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0435 \u043c\u043e\u0436\u0435\u0442 \u0437\u0430\u043d\u044f\u0442\u044c \u043c\u043d\u043e\u0433\u043e \u0432\u0440\u0435\u043c\u0435\u043d\u0438 \u0434\u043b\u044f \u0431\u043e\u043b\u044c\u0448\u0438\u0445 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a. \u041a \u0441\u0447\u0430\u0441\u0442\u044c\u044e, \u0445\u043e\u0440\u043e\u0448\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043f\u0440\u0438\u043c\u0435\u043d\u044f\u0435\u043c\u0430\u044f \u043a \u0441\u0442\u0440\u043e\u043a\u0430\u043c \u0440\u0430\u0437\u0443\u043c\u043d\u043e\u0439 \u0434\u043b\u0438\u043d\u044b, \u043a\u0430\u043a \u043f\u0440\u0430\u0432\u0438\u043b\u043e, \u0438\u043c\u0435\u0435\u0442 \u043c\u0430\u043b\u043e \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0439, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0436\u0438\u0434\u0430\u0435\u043c\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043f\u0440\u0438\u0435\u043c\u043b\u0435\u043c\u044b\u043c.<\/p>\n<p> <\/p>\n<p><em>\u0425\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u044f<\/em><\/p>\n<p> <\/p>\n<p>\u0418\u0441\u0442\u043e\u0447\u043d\u0438\u043a\u043e\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0420\u0430\u0431\u0438\u043d\u0430-\u041a\u0430\u0440\u043f\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0435 \u0432\u044b\u0447\u0438\u0441\u043b\u0435\u043d\u0438\u0435 \u0445\u044d\u0448\u0435\u0439 \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0445 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u0442\u0435\u043a\u0441\u0442\u0430. \u041f\u043e\u043f\u0443\u043b\u044f\u0440\u043d\u043e\u0439 \u0438 \u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u043e\u0439 \u0441\u043a\u043e\u043b\u044c\u0437\u044f\u0449\u0435\u0439 (rolling) \u0445\u044d\u0448-\u0444\u0443\u043d\u043a\u0446\u0438\u0435\u0439 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043e\u0442\u043f\u0435\u0447\u0430\u0442\u043e\u043a \u0420\u0430\u0431\u0438\u043d\u0430 (Rabin fingerprint).<\/p>\n<p> <\/p>\n<p>\u041c\u044b \u0431\u0443\u0434\u0435\u043c \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u0443\u044e \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0430\u044f \u043f\u043e\u0447\u0442\u0438 \u0442\u0430\u043a\u0436\u0435 \u0445\u043e\u0440\u043e\u0448\u0430, \u043a\u0430\u043a \u043e\u0442\u043f\u0435\u0447\u0430\u0442\u043e\u043a \u0420\u0430\u0431\u0438\u043d\u0430. \u041e\u043d\u0430 \u043f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u043a\u0430\u0436\u0434\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0432 \u0447\u0438\u0441\u043b\u043e \u0432 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u043e\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0438, \u043f\u0440\u0438\u0447\u0435\u043c \u043e\u0441\u043d\u043e\u0432\u0430\u043d\u0438\u0435\u043c \u043e\u0431\u044b\u0447\u043d\u043e \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u0431\u043e\u043b\u044c\u0448\u043e\u0435 \u043f\u0440\u043e\u0441\u0442\u043e\u0435 \u0447\u0438\u0441\u043b\u043e.<\/p>\n<p> <\/p>\n<p><em>\u0421\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em><\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u0442\u0435\u043a\u0441\u0442\u0430 \u0434\u043b\u0438\u043d\u043e\u0439 <code>n<\/code> \u0438 \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u0432 <code>p<\/code> \u043e\u0431\u0449\u0435\u0439 \u0434\u043b\u0438\u043d\u043e\u0439 <code>m<\/code> \u0441\u0440\u0435\u0434\u043d\u0435\u0435 \u0438 \u043b\u0443\u0447\u0448\u0435\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(n + m)<\/code> \u0432 \u043f\u0440\u043e\u0441\u0442\u0440\u0430\u043d\u0441\u0442\u0432\u0435 <code>O(p)<\/code>, \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u0440\u0435\u043c\u044f \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(n * m)<\/code>.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0435<\/em><\/p>\n<p> <\/p>\n<p>\u041e\u0434\u043d\u043e \u0438\u0437 \u043f\u0440\u043e\u0441\u0442\u0435\u0439\u0448\u0438\u0445 \u043f\u0440\u0430\u043a\u0442\u0438\u0447\u0435\u0441\u043a\u0438\u0445 \u043f\u0440\u0438\u043c\u0435\u043d\u0435\u043d\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0420\u0430\u0431\u0438\u043d\u0430-\u041a\u0430\u0440\u043f\u0430 \u0441\u043e\u0441\u0442\u043e\u0438\u0442 \u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u0438 \u043f\u043b\u0430\u0433\u0438\u0430\u0442\u0430. \u0410\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043c\u043e\u0436\u0435\u0442 \u0431\u044b\u0441\u0442\u0440\u043e \u043d\u0430\u0445\u043e\u0434\u0438\u0442\u044c \u0432 \u0434\u043e\u043a\u0443\u043c\u0435\u043d\u0442\u0435 \u044d\u043a\u0437\u0435\u043c\u043f\u043b\u044f\u0440\u044b \u043f\u0440\u0435\u0434\u043b\u043e\u0436\u0435\u043d\u0438\u0439 \u0438\u0437 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0442\u0435\u0440\u0438\u0430\u043b\u0430, \u0438\u0433\u043d\u043e\u0440\u0438\u0440\u0443\u044f \u0442\u0430\u043a\u0438\u0435 \u0434\u0435\u0442\u0430\u043b\u0438, \u043a\u0430\u043a \u0440\u0435\u0433\u0438\u0441\u0442\u0440 \u0438 \u043f\u0443\u043d\u043a\u0442\u0443\u0430\u0446\u0438\u044f. \u0412 \u044d\u0442\u043e\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0438\u0437-\u0437\u0430 \u043e\u0431\u0438\u043b\u0438\u044f \u0438\u0441\u043a\u043e\u043c\u044b\u0445 \u0441\u0442\u0440\u043e\u043a \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b \u043e\u0434\u043d\u043e\u0441\u0442\u0440\u043e\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0435\u044d\u0444\u0444\u0435\u043a\u0442\u0438\u0432\u043d\u044b.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u041d\u0430\u0447\u043d\u0435\u043c \u0441 \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0438\u0430\u043b\u044c\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/cryptography\/polynomial-hash.js const DEFAULT_BASE = 37 const DEFAULT_MODULUS = 101  export default class PolynomialHash {   \/**    * @param {number} [base] - \u0411\u0430\u0437\u043e\u0432\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0434\u043b\u044f \u0441\u043e\u0437\u0434\u0430\u043d\u0438\u044f \u043f\u043e\u043b\u0438\u043d\u043e\u043c\u0430.    * @param {number} [modulus] - \u041c\u043e\u0434\u0443\u043b\u044c\u043d\u043e\u0435 \u0447\u0438\u0441\u043b\u043e, \u043a\u043e\u0442\u043e\u0440\u043e\u0435 \u0437\u0430\u0449\u0438\u0449\u0430\u0435\u0442 \u0445\u044d\u0448 \u043e\u0442 \u043f\u0435\u0440\u0435\u043f\u043e\u043b\u043d\u0435\u043d\u0438\u044f.    *\/   constructor({ base = DEFAULT_BASE, modulus = DEFAULT_MODULUS } = {}) {     this.base = base     this.modulus = modulus   }    \/**    * \u0424\u0443\u043d\u043a\u0446\u0438\u044f, \u0441\u043e\u0437\u0434\u0430\u044e\u0449\u0435\u0435 \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441\u043b\u043e\u0432\u0430.    *    * \u0412\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c: O(word.length).    *    * @param {string} word - \u0421\u0442\u0440\u043e\u043a\u0430 \u0434\u043b\u044f \u0445\u044d\u0448\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u044f.    * @return {number}    *\/   hash(word) {     const charCodes = Array.from(word).map((char) =&gt; this.charToNumber(char))      let hash = 0     for (let charIndex = 0; charIndex &lt; charCodes.length; charIndex += 1) {       hash *= this.base       hash += charCodes[charIndex]       hash %= this.modulus     }      return hash   }    \/**    * \u0424\u0443\u043d\u043a\u0446\u0438\u044f, \u0433\u0435\u043d\u0435\u0440\u0438\u0440\u0443\u044e\u0449\u0430\u044f \u0445\u044d\u0448 \u0441\u043b\u043e\u0432\u0430 \u043d\u0430 \u043e\u0441\u043d\u043e\u0432\u0435    * \u0445\u044d\u0448\u0430 \u043f\u0440\u0435\u0434\u044b\u0434\u0443\u0449\u0435\u0433\u043e \u0441\u043b\u043e\u0432\u0430 (\u0441\u0434\u0432\u0438\u043d\u0443\u0442\u043e\u0433\u043e \u043d\u0430 \u043e\u0434\u0438\u043d \u0441\u0438\u043c\u0432\u043e\u043b \u0432\u043b\u0435\u0432\u043e).    *    * \u041f\u043e\u0432\u0442\u043e\u0440\u043d\u043e \u0432\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u0442 \u0445\u044d\u0448 \u0441\u043b\u043e\u0432\u0430, \u0447\u0442\u043e\u0431\u044b \u043d\u0435 \u0430\u043d\u0430\u043b\u0438\u0437\u0438\u0440\u043e\u0432\u0430\u0442\u044c \u0432\u0441\u0435 \u0441\u043b\u043e\u0432\u043e \u0437\u0430\u043d\u043e\u0432\u043e.    *    * \u0412\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c: O(1).    *    * @param {number} prevHash    * @param {string} prevWord    * @param {string} newWord    * @return {number}    *\/   roll(prevHash, prevWord, newWord) {     let hash = prevHash      const prevValue = this.charToNumber(prevWord[0])     const newValue = this.charToNumber(newWord[newWord.length - 1])      let prevValueMultiplier = 1     for (let i = 1; i &lt; prevWord.length; i += 1) {       prevValueMultiplier *= this.base       prevValueMultiplier %= this.modulus     }      hash += this.modulus     hash -= (prevValue * prevValueMultiplier) % this.modulus      hash *= this.base     hash += newValue     hash %= this.modulus      return hash   }    \/**    * \u041f\u0440\u0435\u043e\u0431\u0440\u0430\u0437\u0443\u0435\u0442 \u0441\u0438\u043c\u0432\u043e\u043b \u0432 \u0447\u0438\u0441\u043b\u043e.    *    * @param {string} char    * @return {number}    *\/   charToNumber(char) {     let charCode = char.codePointAt(0)      \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c, \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f \u043b\u0438 \u0441\u0438\u043c\u0432\u043e\u043b \u0441\u0443\u0440\u0440\u043e\u0433\u0430\u0442\u043d\u043e\u0439 \u043f\u0430\u0440\u043e\u0439.     const surrogate = char.codePointAt(1)     if (surrogate !== undefined) {       const surrogateShift = 2 ** 16       charCode += surrogate * surrogateShift     }      return charCode   } }<\/code><\/pre>\n<p> <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u044d\u0442\u0443 \u0444\u0443\u043d\u043a\u0446\u0438\u044e \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0420\u0430\u0431\u0438\u043d\u0430-\u041a\u0430\u0440\u043f\u0430:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/rabin-karp.js import PolynomialHash from '..\/cryptography\/polynomial-hash'  export default function rabinKarp(text, word) {   const hasher = new PolynomialHash()    \/\/ \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0445\u044d\u0448 \u0441\u043b\u043e\u0432\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0439 \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u0434\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0441 \u0445\u044d\u0448\u0430\u043c\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a   const wordHash = hasher.hash(word)    let prevFrame = null   let currentFrameHash = null    \/\/ \u041f\u0435\u0440\u0435\u0431\u0438\u0440\u0430\u0435\u043c \u0432\u0441\u0435 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0442\u0435\u043a\u0441\u0442\u0430, \u043a\u043e\u0442\u043e\u0440\u044b\u0435 \u043c\u043e\u0433\u0443\u0442 \u0441\u043e\u0432\u043f\u0430\u0441\u0442\u044c   for (let i = 0; i &lt; text.length - word.length + 1; i++) {     const currentFrame = text.slice(i, i + word.length)      \/\/ \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0445\u044d\u0448 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438     if (!currentFrameHash) {       currentFrameHash = hasher.hash(currentFrame)     } else {       currentFrameHash = hasher.roll(currentFrameHash, prevFrame, currentFrame)     }      prevFrame = currentFrame      \/\/ \u0421\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0445\u044d\u0448 \u0442\u0435\u043a\u0443\u0449\u0435\u0439 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0441 \u0438\u0441\u043a\u043e\u043c\u044b\u043c \u043f\u0430\u0442\u0442\u0435\u0440\u043d\u043e\u043c.     \/\/ \u041f\u0440\u0438 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0438 \u0445\u044d\u0448\u0435\u0439, \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a \u043d\u0430 \u0441\u043b\u0443\u0447\u0430\u0439 \u043a\u043e\u043b\u043b\u0438\u0437\u0438\u0438 \u0445\u044d\u0448\u0435\u0439     if (       wordHash === currentFrameHash &amp;&amp;       text.slice(i, i + word.length) === word     ) {       return i     }   }    return -1 }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/__tests__\/rabin-karp.test.js import rabinKarp from '..\/rabin-karp'  describe('rabinKarp', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0432 \u0441\u0442\u0440\u043e\u043a\u0435', () =&gt; {     expect(rabinKarp('', '')).toBe(0)     expect(rabinKarp('a', '')).toBe(0)     expect(rabinKarp('a', 'a')).toBe(0)     expect(rabinKarp('ab', 'b')).toBe(1)     expect(rabinKarp('abcbcglx', 'abca')).toBe(-1)     expect(rabinKarp('abcbcglx', 'bcgl')).toBe(3)     expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabcy')).toBe(15)     expect(rabinKarp('abcxabcdabxabcdabcdabcy', 'abcdabca')).toBe(-1)     expect(rabinKarp('abcxabcdabxaabcdabcabcdabcdabcy', 'abcdabca')).toBe(12)     expect(rabinKarp('abcxabcdabxaabaabaaaabcdabcdabcy', 'aabaabaaa')).toBe(11)     expect(rabinKarp(\"^ !\/'#'pp\", \" !\/'#'pp\")).toBe(1)   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0431\u043e\u043b\u044c\u0448\u0438\u043c\u0438 \u0442\u0435\u043a\u0441\u0442\u0430\u043c\u0438', () =&gt; {     const text =       'Lorem Ipsum is simply dummy text of the printing and ' +       \"typesetting industry. Lorem Ipsum has been the industry's standard \" +       'dummy text ever since the 1500s, when an unknown printer took a ' +       'galley of type and scrambled it to make a type specimen book. It ' +       'has survived not only five centuries, but also the leap into ' +       'electronic typesetting, remaining essentially unchanged. It was ' +       'popularised in the 1960s with the release of Letraset sheets ' +       'containing Lorem Ipsum passages, and more recently with desktop' +       'publishing software like Aldus PageMaker including versions of Lorem ' +       'Ipsum.'      expect(rabinKarp(text, 'Lorem')).toBe(0)     expect(rabinKarp(text, 'versions')).toBe(549)     expect(rabinKarp(text, 'versions of Lorem Ipsum.')).toBe(549)     expect(rabinKarp(text, 'versions of Lorem Ipsum:')).toBe(-1)     expect(       rabinKarp(text, 'Lorem Ipsum passages, and more recently with'),     ).toBe(446)   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u0440\u0430\u0431\u043e\u0442\u0430\u0442\u044c \u0441 \u0441\u0438\u043c\u0432\u043e\u043b\u0430\u043c\u0438 UTF', () =&gt; {     expect(rabinKarp('a\\u{ffff}', '\\u{ffff}')).toBe(1)     expect(rabinKarp('\\u0000\u8000\\u0000', '\u8000\\u0000')).toBe(1)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/strings\/__tests__\/rabin-karp<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/zc\/nn\/ma\/zcnnmaofqwh4oitjdzq8bpa5y9k.png\" data-src=\"https:\/\/habrastorage.org\/webt\/zc\/nn\/ma\/zcnnmaofqwh4oitjdzq8bpa5y9k.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-naibolshaya-obschaya-podstroka\">\u276f \u041d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043e\u0431\u0449\u0430\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9D%D0%B0%D0%B8%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%B0%D1%8F_%D0%BE%D0%B1%D1%89%D0%B0%D1%8F_%D0%BF%D0%BE%D0%B4%D1%81%D1%82%D1%80%D0%BE%D0%BA%D0%B0\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=BysNXJHzCEs\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u041d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0430\u044f \u043e\u0431\u0449\u0430\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 (longest common substring) \u2014 \u044d\u0442\u043e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u0434\u0432\u0443\u0445 \u0438\u043b\u0438 \u0431\u043e\u043b\u0435\u0435 \u0441\u0442\u0440\u043e\u043a, \u0438\u043c\u0435\u044e\u0449\u0430\u044f \u043c\u0430\u043a\u0441\u0438\u043c\u0430\u043b\u044c\u043d\u0443\u044e \u0434\u043b\u0438\u043d\u0443. \u041d\u0435 \u043f\u0443\u0442\u0430\u0439\u0442\u0435 \u0441 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0435\u0439 \u043e\u0431\u0449\u0435\u0439 \u043f\u043e\u0434\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u0441\u0442\u044c\u044e.<\/p>\n<p> <\/p>\n<p><em>\u041f\u0440\u0438\u043c\u0435\u0440<\/em><\/p>\n<p> <\/p>\n<p>\u041d\u041e\u041f \u0441\u0442\u0440\u043e\u043a <code>ABABC<\/code>, <code>BABCA<\/code> \u0438 <code>ABCBA<\/code> \u2014 \u0441\u0442\u0440\u043e\u043a\u0430 <code>ABC<\/code> \u0434\u043b\u0438\u043d\u043e\u0439 <code>3<\/code>. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u043e\u0431\u0449\u0438\u043c\u0438 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u044f\u0432\u043b\u044f\u044e\u0442\u0441\u044f <code>A<\/code>, <code>AB<\/code>, <code>B<\/code>, <code>BA<\/code>, <code>BC<\/code> \u0438 <code>C<\/code>.<\/p>\n<p> <\/p>\n<pre><code class=\"plaintext\">ABABC   |||  BABCA   |||   ABCBA<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/longest-common-substring.js export default function longestCommonSubstring(str1, str2) {   const s1 = [...str1]   const s2 = [...str2]    const matrix = new Array(s2.length + 1)     .fill(null)     .map(() =&gt; new Array(s1.length + 1).fill(null))    \/\/ \u0417\u0430\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043f\u0435\u0440\u0432\u0443\u044e \u0441\u0442\u0440\u043e\u043a\u0443 \u0438 \u043f\u0435\u0440\u0432\u0443\u044e \u043a\u043e\u043b\u043e\u043d\u043a\u0443 `0`   for (let columnIndex = 0; columnIndex &lt;= s1.length; columnIndex++) {     matrix[0][columnIndex] = 0   }   for (let rowIndex = 0; rowIndex &lt;= s2.length; rowIndex++) {     matrix[rowIndex][0] = 0   }    let longestSubstringLength = 0   let longestSubstringColumn = 0   let longestSubstringRow = 0    for (let rowIndex = 1; rowIndex &lt;= s2.length; rowIndex++) {     for (let columnIndex = 1; columnIndex &lt;= s1.length; columnIndex++) {       if (s1[columnIndex - 1] === s2[rowIndex - 1]) {         matrix[rowIndex][columnIndex] =           matrix[rowIndex - 1][columnIndex - 1] + 1       } else {         matrix[rowIndex][columnIndex] = 0       }        \/\/ \u0418\u0449\u0435\u043c \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0443\u044e \u0434\u043b\u0438\u043d\u0443       if (matrix[rowIndex][columnIndex] &gt; longestSubstringLength) {         longestSubstringLength = matrix[rowIndex][columnIndex]         longestSubstringColumn = columnIndex         longestSubstringRow = rowIndex       }     }   }    \/\/ \u0421\u0430\u043c\u0430\u044f \u0434\u043b\u0438\u043d\u043d\u0430\u044f \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0430 \u043d\u0435 \u043d\u0430\u0439\u0434\u0435\u043d\u0430   if (longestSubstringLength === 0) {     return ''   }    \/\/ \u0418\u0437\u0432\u043b\u0435\u043a\u0430\u0435\u043c \u0441\u0430\u043c\u0443\u044e \u0434\u043b\u0438\u043d\u043d\u0443\u044e \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0443 \u0438\u0437 \u043c\u0430\u0442\u0440\u0438\u0446\u044b   \/\/ \u043f\u0443\u0442\u0435\u043c \u043a\u043e\u043d\u043a\u0430\u0442\u0435\u043d\u0430\u0446\u0438\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u043e\u0432   let longestSubstring = ''    while (matrix[longestSubstringRow][longestSubstringColumn] &gt; 0) {     longestSubstring = s1[longestSubstringColumn - 1] + longestSubstring     longestSubstringColumn--     longestSubstringRow--   }    return longestSubstring }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/strings\/__tests__\/longest-common-substring.test.js import longestCommonSubstring from '..\/longest-common-substring'  describe('longestCommonSubstring', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043d\u0430\u0438\u0431\u043e\u043b\u044c\u0448\u0438\u0435 \u043e\u0431\u0449\u0438\u0435 \u043f\u043e\u0434\u0441\u0442\u0440\u043e\u043a\u0438 \u0434\u0432\u0443\u0445 \u0441\u0442\u0440\u043e\u043a', () =&gt; {     expect(longestCommonSubstring('', '')).toBe('')     expect(longestCommonSubstring('ABC', '')).toBe('')     expect(longestCommonSubstring('', 'ABC')).toBe('')     expect(longestCommonSubstring('ABABC', 'BABCA')).toBe('BABC')     expect(longestCommonSubstring('BABCA', 'ABCBA')).toBe('ABC')     expect(longestCommonSubstring('sea', 'eat')).toBe('ea')     expect(longestCommonSubstring('algorithms', 'rithm')).toBe('rithm')     expect(       longestCommonSubstring(         'Algorithms and data structures implemented in JavaScript',         'Here you may find Algorithms and data structures that are implemented in JavaScript',       ),     ).toBe('Algorithms and data structures ')   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043f\u0440\u0430\u0432\u0438\u043b\u044c\u043d\u043e \u043e\u0431\u0440\u0430\u0431\u0430\u0442\u044b\u0432\u0430\u0442\u044c\u0441\u044f \u044e\u043d\u0438\u043a\u043e\u0434', () =&gt; {     expect(longestCommonSubstring('\ud800\udf35\ud800\udf35**ABC', '\ud800\udf35\ud800\udf35--ABC')).toBe('ABC')     expect(longestCommonSubstring('\ud800\udf35\ud800\udf35**A', '\ud800\udf35\ud800\udf35--A')).toBe('\ud800\udf35\ud800\udf35')     expect(longestCommonSubstring('A\u4e70B\u65f6', '\u4e70B\u65f6GD')).toBe('\u4e70B\u65f6')     expect(       longestCommonSubstring('After test\u4e70\u65f6 case', 'another_test\u4e70\u65f6'),     ).toBe('test\u4e70\u65f6')   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/strings\/__tests__\/longest-common-substring<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/i2\/q_\/dp\/i2q_dpebr_kqeqgokj_l97kxbmk.png\" data-src=\"https:\/\/habrastorage.org\/webt\/i2\/q_\/dp\/i2q_dpebr_kqeqgokj_l97kxbmk.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h1 id=\"-poisk\">\u276f \u041f\u043e\u0438\u0441\u043a<\/h1>\n<p> <\/p>\n<h2 id=\"-lineynyy-poisk\">\u276f \u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%9B%D0%B8%D0%BD%D0%B5%D0%B9%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=bmhWdD0hK7s\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 (\u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u044b\u0439) \u043f\u043e\u0438\u0441\u043a (linear search) \u2014 \u044d\u0442\u043e \u043c\u0435\u0442\u043e\u0434 \u043f\u043e\u0438\u0441\u043a\u0430 \u0446\u0435\u043b\u0435\u0432\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0432 \u0441\u043f\u0438\u0441\u043a\u0435 (\u043c\u0430\u0441\u0441\u0438\u0432\u0435). \u041e\u043d \u043f\u043e\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u043d\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u0442 \u043a\u0430\u0436\u0434\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0441\u043f\u0438\u0441\u043a\u0430 \u043d\u0430 \u043f\u0440\u0435\u0434\u043c\u0435\u0442 \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u044f \u0441 \u0446\u0435\u043b\u0435\u0432\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u0434\u043e \u0442\u0435\u0445 \u043f\u043e\u0440, \u043f\u043e\u043a\u0430 \u043b\u0438\u0431\u043e \u043d\u0435 \u0431\u0443\u0434\u0435\u0442 \u043d\u0430\u0439\u0434\u0435\u043d\u043e \u0441\u043e\u0432\u043f\u0430\u0434\u0435\u043d\u0438\u0435, \u043b\u0438\u0431\u043e \u043d\u0435 \u0437\u0430\u043a\u043e\u043d\u0447\u0430\u0442\u0441\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u044b. \u041b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u0437\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0435 \u0432\u0440\u0435\u043c\u044f \u0438 \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442 <code>n<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439, \u0433\u0434\u0435 <code>n<\/code> \u2014 \u044d\u0442\u043e \u0434\u043b\u0438\u043d\u0430 \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u0422\u0430\u043a\u0438\u043c \u043e\u0431\u0440\u0430\u0437\u043e\u043c, <em>\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em> \u0434\u0430\u043d\u043d\u043e\u0433\u043e \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(n)<\/code>.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/webt\/lu\/s9\/29\/lus929vsniktif5sj_snhvt4aau.gif\" data-src=\"https:\/\/habrastorage.org\/webt\/lu\/s9\/29\/lus929vsniktif5sj_snhvt4aau.gif\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0441\u043f\u0438\u0441\u043a\u0430 \u0441 \u0446\u0435\u043b\u0435\u0432\u044b\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u0431\u0443\u0434\u0435\u0442 \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u043e\u0432\u0430\u0442\u044c\u0441\u044f \u043a\u0430\u0441\u0442\u043e\u043c\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f, \u043a\u043e\u0442\u043e\u0440\u0443\u044e \u043c\u044b \u0440\u0430\u0441\u0441\u043c\u0430\u0442\u0440\u0438\u0432\u0430\u043b\u0438 \u0432 \u0441\u0430\u043c\u043e\u0439 \u043f\u0435\u0440\u0432\u043e\u0439 \u0441\u0442\u0430\u0442\u044c\u0435 \u0441\u0435\u0440\u0438\u0438. \u041d\u0430\u043f\u043e\u043c\u043d\u044e, \u043a\u0430\u043a \u043e\u043d\u0430 \u0432\u044b\u0433\u043b\u044f\u0434\u0438\u0442:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ utils\/Comparator.js export default class Comparator {   constructor(fn) {     this.compare = fn || Comparator.defaultCompare   }    \/\/ \u0414\u0435\u0444\u043e\u043b\u0442\u043d\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u0443\u0437\u043b\u043e\u0432   static defaultCompare(a, b) {     if (a === b) {       return 0     }     return a &lt; b ? -1 : 1   }    \/\/ \u041f\u0440\u043e\u0432\u0435\u0440\u043a\u0430 \u043d\u0430 \u0440\u0430\u0432\u0435\u043d\u0441\u0442\u0432\u043e   equal(a, b) {     return this.compare(a, b) === 0   }    \/\/ \u041c\u0435\u043d\u044c\u0448\u0435 \u0447\u0435\u043c   lessThan(a, b) {     return this.compare(a, b) &lt; 0   }    \/\/ \u0411\u043e\u043b\u044c\u0448\u0435 \u0447\u0435\u043c   greaterThan(a, b) {     return this.compare(a, b) &gt; 0   }    \/\/ \u041c\u0435\u043d\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u043d\u043e   lessThanOrEqual(a, b) {     return this.lessThan(a, b) || this.equal(a, b)   }    \/\/ \u0411\u043e\u043b\u044c\u0448\u0435 \u0438\u043b\u0438 \u0440\u0430\u0432\u043d\u043e   greaterThanOrEqual(a, b) {     return this.greaterThan(a, b) || this.equal(a, b)   }    \/\/ \u0418\u043d\u0432\u0435\u0440\u0441\u0438\u044f \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f   reverse() {     const original = this.compare     this.compare = (a, b) =&gt; original(b, a)   } }<\/code><\/pre>\n<p> <\/p>\n<p>\u042d\u0442\u0430 \u0444\u0443\u043d\u043a\u0446\u0438\u044f \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0442\u044c \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e \u043f\u0440\u0438\u043c\u0438\u0442\u0438\u0432\u043d\u044b\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043d\u043e \u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u044b.<\/p>\n<p> <\/p>\n<p>\u0418\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u043c \u0435\u0435 \u0434\u043b\u044f \u0440\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/linear-search.js import Comparator from '..\/..\/utils\/comparator'  export default function linearSearch(arr, target, fn) {   const comparator = new Comparator(fn)   const result = []    arr.forEach((item, index) =&gt; {     if (comparator.equal(item, target)) {       result.push(index)     }   })    return result }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/__tests__\/linear-search.test.js import linearSearch from '..\/linear-search'  describe('linearSearch', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0447\u0438\u0441\u043b\u0430 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435', () =&gt; {     const array = [1, 2, 4, 6, 2]      expect(linearSearch(array, 10)).toEqual([])     expect(linearSearch(array, 1)).toEqual([0])     expect(linearSearch(array, 2)).toEqual([1, 4])   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0441\u0438\u043c\u0432\u043e\u043b\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435', () =&gt; {     const array = ['a', 'b', 'a']      expect(linearSearch(array, 'c')).toEqual([])     expect(linearSearch(array, 'b')).toEqual([1])     expect(linearSearch(array, 'a')).toEqual([0, 2])   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435', () =&gt; {     const comparatorCallback = (a, b) =&gt; {       if (a.key === b.key) {         return 0       }        return a.key &lt;= b.key ? -1 : 1     }      const array = [{ key: 5 }, { key: 6 }, { key: 7 }, { key: 6 }]      expect(linearSearch(array, { key: 10 }, comparatorCallback)).toEqual([])     expect(linearSearch(array, { key: 5 }, comparatorCallback)).toEqual([0])     expect(linearSearch(array, { key: 6 }, comparatorCallback)).toEqual([1, 3])   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/searches\/__tests__\/linear-search<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/uv\/vc\/nf\/uvvcnfwtt6jog8c3o18253emqrm.png\" data-src=\"https:\/\/habrastorage.org\/webt\/uv\/vc\/nf\/uvvcnfwtt6jog8c3o18253emqrm.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-poisk-s-perehodom\">\u276f \u041f\u043e\u0438\u0441\u043a \u0441 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u043c<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Jump_search\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/jump-search\/\">GeekForGeeks<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u041f\u043e\u0438\u0441\u043a \u0441 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u043c (\u0431\u043b\u043e\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a) (jump\/block search) \u2014 \u044d\u0442\u043e \u043f\u043e\u0438\u0441\u043a\u043e\u0432\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u0434\u043b\u044f \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u0432. \u041e\u0441\u043d\u043e\u0432\u043d\u0430\u044f \u0438\u0434\u0435\u044f \u0437\u0430\u043a\u043b\u044e\u0447\u0430\u0435\u0442\u0441\u044f \u0432 \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0435 \u043c\u0435\u043d\u044c\u0448\u0435\u0433\u043e \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 (\u0447\u0435\u043c \u043f\u0440\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0435) \u0437\u0430 \u0441\u0447\u0435\u0442 \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432 \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u043d\u044b\u043c\u0438 \u0448\u0430\u0433\u0430\u043c\u0438 \u0438\u043b\u0438 \u043f\u0440\u043e\u043f\u0443\u0441\u043a\u0430 \u043d\u0435\u043a\u043e\u0442\u043e\u0440\u044b\u0445 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432, \u0432\u043c\u0435\u0441\u0442\u043e \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438 \u0432\u0441\u0435\u0445.<\/p>\n<p> <\/p>\n<p>\u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0443 \u043d\u0430\u0441 \u0435\u0441\u0442\u044c \u043c\u0430\u0441\u0441\u0438\u0432 <code>arr<\/code> \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c <code>n<\/code> \u0438 \u0431\u043b\u043e\u043a (\u0434\u043b\u044f \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0430) \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c <code>m<\/code>. \u041c\u044b \u043f\u0440\u043e\u0432\u0435\u0440\u044f\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441\u044b <code>arr[0]<\/code>, <code>arr[m]<\/code>, <code>arr[2 * m]<\/code>, &#8230;, <code>arr[k * m]<\/code>, \u043f\u043e\u043a\u0430 \u043d\u0435 \u043d\u0430\u0439\u0434\u0435\u043c \u0438\u043d\u0442\u0435\u0440\u0432\u0430\u043b <code>arr[k * m] &lt; x &lt; arr[(k+1) * m]<\/code>, \u0433\u0434\u0435 <code>x<\/code> \u2014 \u0438\u0441\u043a\u043e\u043c\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435. \u0417\u0430\u0442\u0435\u043c \u0434\u043b\u044f \u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f <code>x<\/code> \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u0442\u0441\u044f \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441 \u0438\u043d\u0434\u0435\u043a\u0441\u0430 <code>k * m<\/code>.<\/p>\n<p> <\/p>\n<p>\u041a\u0430\u043a\u043e\u0432 \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0440\u0430\u0437\u043c\u0435\u0440 \u0431\u043b\u043e\u043a\u0430? \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u043d\u0430\u043c \u043f\u0440\u0438\u0434\u0435\u0442\u0441\u044f \u0432\u044b\u043f\u043e\u043b\u043d\u0438\u0442\u044c <code>n\/m<\/code> \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u043e\u0432, \u0438 \u0435\u0441\u043b\u0438 \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u0435 \u043f\u0440\u043e\u0432\u0435\u0440\u0435\u043d\u043d\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u043e\u043b\u044c\u0448\u0435, \u0447\u0435\u043c \u0438\u0441\u043a\u043e\u043c\u043e\u0435, \u043c\u044b \u0432\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c <code>m - 1<\/code> \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>((n\/m) + m - 1)<\/code>. \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 <code>((n\/m) + m - 1)<\/code> \u0431\u0443\u0434\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043f\u0440\u0438 <code>m = \u221an<\/code>. \u041f\u043e\u044d\u0442\u043e\u043c\u0443 \u043b\u0443\u0447\u0448\u0438\u043c \u0440\u0430\u0437\u043c\u0435\u0440\u043e\u043c \u0431\u043b\u043e\u043a\u0430 \u044f\u0432\u043b\u044f\u0435\u0442\u0441\u044f <code>\u221an<\/code>. \u042d\u0442\u043e \u043e\u043f\u0440\u0435\u0434\u0435\u043b\u044f\u0435\u0442 <em>\u0432\u0440\u0435\u043c\u0435\u043d\u043d\u0443\u044e \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em> \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u2014 <code>O(\u221an)<\/code>.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/jump-search.js import Comparator from '..\/..\/utils\/comparator'  export default function jumpSearch(sortedArr, target, fn) {   const comparator = new Comparator(fn)   const length = sortedArr.length   if (!length) return -1    \/\/ \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u043e\u043f\u0442\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u0439 \u0448\u0430\u0433.   \/\/ \u041e\u0431\u0449\u0435\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u0439 \u0432 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 \u0431\u0443\u0434\u0435\u0442 ((length\/step) + step - 1).   \/\/ \u0417\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 ((length\/step) + step - 1) \u0431\u0443\u0434\u0435\u0442 \u043c\u0438\u043d\u0438\u043c\u0430\u043b\u044c\u043d\u044b\u043c \u043f\u0440\u0438 step = \u221alength   let step = Math.floor(Math.sqrt(length))    let start = 0   let end = step    \/\/ \u0418\u0449\u0435\u043c \u0431\u043b\u043e\u043a, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442 \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442   while (comparator.greaterThan(target, sortedArr[Math.min(end, length) - 1])) {     \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u043c\u0443 \u0431\u043b\u043e\u043a\u0443     start = end     end += step      if (start &gt; length) return -1   }    \/\/ \u0412\u044b\u043f\u043e\u043b\u043d\u044f\u0435\u043c \u043b\u0438\u043d\u0435\u0439\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0432 \u0431\u043b\u043e\u043a\u0435, \u043a \u043a\u043e\u0442\u043e\u0440\u043e\u043c\u0443 \u043f\u0440\u0438\u043d\u0430\u0434\u043b\u0435\u0436\u0438\u0442   \/\/ `target`, \u043d\u0430\u0447\u0438\u043d\u0430\u044f \u0441\u043e `start`   let currentIndex = start   while (currentIndex &lt; Math.min(end, length)) {     if (comparator.equal(target, sortedArr[currentIndex])) {       return currentIndex     }     currentIndex++   }    return -1 }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/__tests__\/jump-search.test.js import jumpSearch from '..\/jump-search'  describe('jumpSearch', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0447\u0438\u0441\u043b\u0430 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445', () =&gt; {     expect(jumpSearch([], 1)).toBe(-1)     expect(jumpSearch([1], 2)).toBe(-1)     expect(jumpSearch([1], 1)).toBe(0)     expect(jumpSearch([1, 2], 1)).toBe(0)     expect(jumpSearch([1, 2], 1)).toBe(0)     expect(jumpSearch([1, 1, 1], 1)).toBe(0)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 2)).toBe(1)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 0)).toBe(-1)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 0)).toBe(-1)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 7)).toBe(-1)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 5)).toBe(2)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 20)).toBe(4)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 30)).toBe(7)     expect(jumpSearch([1, 2, 5, 10, 20, 21, 24, 30, 48], 48)).toBe(8)   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435', () =&gt; {     const sortedArrayOfObjects = [       { key: 1, value: 'value1' },       { key: 2, value: 'value2' },       { key: 3, value: 'value3' },     ]      const comparator = (a, b) =&gt; {       if (a.key === b.key) return 0       return a.key &lt; b.key ? -1 : 1     }      expect(jumpSearch([], { key: 1 }, comparator)).toBe(-1)     expect(jumpSearch(sortedArrayOfObjects, { key: 4 }, comparator)).toBe(-1)     expect(jumpSearch(sortedArrayOfObjects, { key: 1 }, comparator)).toBe(0)     expect(jumpSearch(sortedArrayOfObjects, { key: 2 }, comparator)).toBe(1)     expect(jumpSearch(sortedArrayOfObjects, { key: 3 }, comparator)).toBe(2)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/searches\/__tests__\/jump-search<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/ir\/j9\/ec\/irj9ecrp_6e0vq6oztqxpwajzdo.png\" data-src=\"https:\/\/habrastorage.org\/webt\/ir\/j9\/ec\/irj9ecrp_6e0vq6oztqxpwajzdo.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<h2 id=\"-dvoichnyy-poisk\">\u276f \u0414\u0432\u043e\u0438\u0447\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.youtube.com\/watch?v=aFoaeA2tsVQ\">YouTube<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0414\u0432\u043e\u0438\u0447\u043d\u044b\u0439 (\u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0439) \u043f\u043e\u0438\u0441\u043a (\u043c\u0435\u0442\u043e\u0434 \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043f\u043e\u043f\u043e\u043b\u0430\u043c \u0438\u043b\u0438 \u0434\u0438\u0445\u043e\u0442\u043e\u043c\u0438\u044f) (binary\/half-interval\/logarithmic search, binary chop) -\u044d\u0442\u043e \u043a\u043b\u0430\u0441\u0441\u0438\u0447\u0435\u0441\u043a\u0438\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u043e\u0438\u0441\u043a\u0430 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435 (\u0432\u0435\u043a\u0442\u043e\u0440\u0435), \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u044e\u0449\u0438\u0439 \u0434\u0440\u043e\u0431\u043b\u0435\u043d\u0438\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430 \u043d\u0430 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u044b. \u0421\u0443\u0442\u044c \u0442\u0430\u043a\u0430\u044f: \u043c\u044b \u0441\u0440\u0430\u0432\u043d\u0438\u0432\u0430\u0435\u043c \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0441 \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u044b\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u0415\u0441\u043b\u0438 \u043e\u043d\u0438 \u043d\u0435\u0440\u0430\u0432\u043d\u044b, \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0430, \u0432 \u043a\u043e\u0442\u043e\u0440\u043e\u0439 \u0442\u043e\u0447\u043d\u043e \u043d\u0435\u0442 \u0446\u0435\u043b\u0435\u0432\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f, \u043e\u0442\u0431\u0440\u0430\u0441\u044b\u0432\u0430\u0435\u0442\u0441\u044f, \u0438 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0434\u043e\u043b\u0436\u0430\u0435\u0442\u0441\u044f \u0432 \u0434\u0440\u0443\u0433\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043f\u043e \u0442\u0430\u043a\u043e\u043c\u0443 \u0436\u0435 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0443. \u0415\u0441\u043b\u0438 \u043f\u043e\u0438\u0441\u043a \u0437\u0430\u0432\u0435\u0440\u0448\u0438\u043b\u0441\u044f \u043f\u0443\u0441\u0442\u044b\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u043e\u043c, \u0437\u043d\u0430\u0447\u0438\u0442, \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442.<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/c0\/_y\/ns\/c0_ynsayhjh1msnteus7dydzuzo.png\" data-src=\"https:\/\/habrastorage.org\/webt\/c0\/_y\/ns\/c0_ynsayhjh1msnteus7dydzuzo.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p><em>\u0412\u0440\u0435\u043c\u0435\u043d\u043d\u0430\u044f \u0441\u043b\u043e\u0436\u043d\u043e\u0441\u0442\u044c<\/em> \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430 \u0441\u043e\u0441\u0442\u0430\u0432\u043b\u044f\u0435\u0442 <code>O(log(n))<\/code>, \u043f\u043e\u0441\u043a\u043e\u043b\u044c\u043a\u0443 \u043c\u044b \u0443\u043c\u0435\u043d\u044c\u0448\u0430\u0435\u043c \u043f\u043b\u043e\u0449\u0430\u0434\u044c \u043f\u043e\u0438\u0441\u043a\u0430 \u0432\u0434\u0432\u043e\u0435 \u043d\u0430 \u043a\u0430\u0436\u0434\u043e\u0439 \u0438\u0442\u0435\u0440\u0430\u0446\u0438\u0438.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/binary-search.js import Comparator from '..\/..\/utils\/comparator'  export default function binarySearch(sortedArr, target, fn) {   const comparator = new Comparator(fn)    let start = 0   let end = sortedArr.length - 1    while (start &lt;= end) {     \/\/ \u0412\u044b\u0447\u0438\u0441\u043b\u044f\u0435\u043c \u0438\u043d\u0434\u0435\u043a\u0441 \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430     let middle = start + Math.floor((end - start) \/ 2)      if (comparator.equal(sortedArr[middle], target)) {       return middle     }      \/\/ \u0415\u0441\u043b\u0438 \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u043c\u0435\u043d\u044c\u0448\u0435 \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430     if (comparator.lessThan(sortedArr[middle], target)) {       \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043f\u0440\u0430\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430       start = middle + 1     } else {       \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043b\u0435\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430       end = middle - 1     }   }    return -1 }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/__tests__\/binary-search.test.js import binarySearch from '..\/binary-search'  describe('binarySearch', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0447\u0438\u0441\u043b\u0430 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445', () =&gt; {     expect(binarySearch([], 1)).toBe(-1)     expect(binarySearch([1], 1)).toBe(0)     expect(binarySearch([1, 2], 1)).toBe(0)     expect(binarySearch([1, 2], 2)).toBe(1)     expect(binarySearch([1, 5, 10, 12], 1)).toBe(0)     expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 17)).toBe(5)     expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 1)).toBe(0)     expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 100)).toBe(7)     expect(binarySearch([1, 5, 10, 12, 14, 17, 22, 100], 0)).toBe(-1)   })    it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u043e\u0431\u044a\u0435\u043a\u0442\u044b \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u043e\u043c \u043c\u0430\u0441\u0441\u0438\u0432\u0435', () =&gt; {     const sortedArrayOfObjects = [       { key: 1, value: 'value1' },       { key: 2, value: 'value2' },       { key: 3, value: 'value3' },     ]      const comparator = (a, b) =&gt; {       if (a.key === b.key) return 0       return a.key &lt; b.key ? -1 : 1     }      expect(binarySearch([], { key: 1 }, comparator)).toBe(-1)     expect(binarySearch(sortedArrayOfObjects, { key: 4 }, comparator)).toBe(-1)     expect(binarySearch(sortedArrayOfObjects, { key: 1 }, comparator)).toBe(0)     expect(binarySearch(sortedArrayOfObjects, { key: 2 }, comparator)).toBe(1)     expect(binarySearch(sortedArrayOfObjects, { key: 3 }, comparator)).toBe(2)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/searches\/__tests__\/binary-search<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/eu\/zu\/ok\/euzuoklqoskn2emaveuxx_b7wws.png\" data-src=\"https:\/\/habrastorage.org\/webt\/eu\/zu\/ok\/euzuoklqoskn2emaveuxx_b7wws.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u0422\u0430\u043a\u0438\u0435 \u0432\u0430\u0440\u0438\u0430\u043d\u0442\u044b \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u0433\u043e \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u0440\u0435\u0434\u043b\u0430\u0433\u0430\u044e\u0442 \u0440\u0430\u0437\u0440\u0430\u0431\u043e\u0442\u0447\u0438\u043a\u0438 VSCode:<\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ https:\/\/github.com\/microsoft\/vscode\/blob\/main\/src\/vs\/base\/common\/arrays.ts#L73 export function binarySearch(array, key, comparator) {     return binarySearch2(array.length, i =&gt; comparator(array[i], key)); }  \/\/ \u041d\u0435 \u043e\u0447\u0435\u043d\u044c \u043f\u043e\u043d\u044f\u0442\u043d\u043e, \u0437\u0430\u0447\u0435\u043c \u043d\u0443\u0436\u043d\u0430 \u043f\u0435\u0440\u0432\u0430\u044f \u0444\u0443\u043d\u043a\u0446\u0438\u044f export function binarySearch2(length, compareToKey) {     let low = 0,         high = length - 1;      while (low &lt;= high) {         const mid = ((low + high) \/ 2) | 0;         const comp = compareToKey(mid);         if (comp &lt; 0) {             low = mid + 1;         } else if (comp &gt; 0) {             high = mid - 1;         } else {             return mid;         }     }     return -(low + 1); }  \/\/ \u0422\u043e\u0436\u0435 \u0441\u0430\u043c\u043e\u0435, \u043d\u043e \u0432 \u0444\u043e\u0440\u043c\u0435 \u043e\u0434\u043d\u043e\u0439 \u0444\u0443\u043d\u043a\u0446\u0438\u0438 \/\/ https:\/\/github.com\/microsoft\/vscode\/blob\/main\/extensions\/html-language-features\/server\/src\/utils\/arrays.ts#L60 export function binarySearch(array, key, comparator) {     let low = 0,         high = array.length - 1;      while (low &lt;= high) {         const mid = ((low + high) \/ 2) | 0;         const comp = comparator(array[mid], key);         if (comp &lt; 0) {             low = mid + 1;         } else if (comp &gt; 0) {             high = mid - 1;         } else {             return mid;         }     }     return -(low + 1); }<\/code><\/pre>\n<p> <\/p>\n<h2 id=\"-interpolyacionnyy-poisk\">\u276f \u0418\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a<\/h2>\n<p> <\/p>\n<p><strong>\u041e\u043f\u0438\u0441\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<ul>\n<li><a href=\"https:\/\/ru.wikipedia.org\/wiki\/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA\">\u0412\u0438\u043a\u0438\u043f\u0435\u0434\u0438\u044f<\/a><\/li>\n<li><a href=\"https:\/\/www.geeksforgeeks.org\/interpolation-search\/\">GeeksForGeeks<\/a><\/li>\n<\/ul>\n<p> <\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u043e\u043d\u043d\u044b\u0439 (\u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0439) \u043f\u043e\u0438\u0441\u043a (interpolation search) \u043e\u0441\u043d\u043e\u0432\u0430\u043d \u043d\u0430 \u043f\u0440\u0438\u043d\u0446\u0438\u043f\u0435 \u043f\u043e\u0438\u0441\u043a\u0430 \u0432 \u0442\u0435\u043b\u0435\u0444\u043e\u043d\u043d\u043e\u0439 \u043a\u043d\u0438\u0433\u0435 \u0438\u043b\u0438, \u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0432 \u0441\u043b\u043e\u0432\u0430\u0440\u0435. \u0412\u043c\u0435\u0441\u0442\u043e \u0441\u0440\u0430\u0432\u043d\u0435\u043d\u0438\u044f \u043a\u0430\u0436\u0434\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0441 \u0438\u0441\u043a\u043e\u043c\u044b\u043c, \u043a\u0430\u043a \u043f\u0440\u0438 \u043b\u0438\u043d\u0435\u0439\u043d\u043e\u043c \u043f\u043e\u0438\u0441\u043a\u0435, \u0434\u0430\u043d\u043d\u044b\u0439 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0435 \u043c\u0435\u0441\u0442\u043e\u043d\u0430\u0445\u043e\u0436\u0434\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430: \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0438\u0441\u0445\u043e\u0434\u0438\u0442 \u043f\u043e\u0434\u043e\u0431\u043d\u043e \u0434\u0432\u043e\u0438\u0447\u043d\u043e\u043c\u0443, \u043d\u043e \u0432\u043c\u0435\u0441\u0442\u043e \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043d\u0430 \u0434\u0432\u0435 \u0447\u0430\u0441\u0442\u0438, \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442 \u043e\u0446\u0435\u043d\u043a\u0443 \u043d\u043e\u0432\u043e\u0439 \u043e\u0431\u043b\u0430\u0441\u0442\u0438 \u043f\u043e\u0438\u0441\u043a\u0430 \u043f\u043e \u0440\u0430\u0441\u0441\u0442\u043e\u044f\u043d\u0438\u044e \u043c\u0435\u0436\u0434\u0443 \u043a\u043b\u044e\u0447\u043e\u043c \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430. \u0414\u0440\u0443\u0433\u0438\u043c\u0438 \u0441\u043b\u043e\u0432\u0430\u043c\u0438, \u0431\u0438\u043d\u0430\u0440\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u043b\u0438\u0448\u044c \u0437\u043d\u0430\u043a \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u0438 \u043c\u0435\u0436\u0434\u0443 \u043a\u043b\u044e\u0447\u043e\u043c \u0438 \u0442\u0435\u043a\u0443\u0449\u0438\u043c \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435\u043c, \u0430 \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u0435\u0449\u0435 \u0443\u0447\u0438\u0442\u044b\u0432\u0430\u0435\u0442 \u0438 \u043c\u043e\u0434\u0443\u043b\u044c \u044d\u0442\u043e\u0439 \u0440\u0430\u0437\u043d\u043e\u0441\u0442\u0438 \u0438 \u043f\u043e \u0434\u0430\u043d\u043d\u043e\u043c\u0443 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044e \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442 \u043f\u0440\u0435\u0434\u0441\u043a\u0430\u0437\u0430\u043d\u0438\u0435 \u043f\u043e\u0437\u0438\u0446\u0438\u0438 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u0434\u043b\u044f \u043f\u0440\u043e\u0432\u0435\u0440\u043a\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0435\u0441\u043b\u0438 \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 \u0431\u043b\u0438\u0436\u0435 \u043a \u043f\u043e\u0441\u043b\u0435\u0434\u043d\u0435\u043c\u0443 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0443 \u043c\u0430\u0441\u0441\u0438\u0432\u0430, \u043f\u043e\u0438\u0441\u043a \u043d\u0430\u0447\u043d\u0435\u0442\u0441\u044f \u0441 \u0431\u043b\u043e\u043a\u0430, \u043d\u0430\u0445\u043e\u0434\u044f\u0449\u0435\u0433\u043e\u0441\u044f \u0432 \u043a\u043e\u043d\u0446\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430.<\/p>\n<p> <\/p>\n<p>\u0414\u043b\u044f \u043f\u043e\u0438\u0441\u043a\u0430 \u0446\u0435\u043b\u0435\u0432\u043e\u0433\u043e \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u0438\u0441\u043f\u043e\u043b\u044c\u0437\u0443\u0435\u0442\u0441\u044f \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0430\u044f \u0444\u043e\u0440\u043c\u0443\u043b\u0430:<\/p>\n<p> <\/p>\n<pre><code class=\"plaintext\">\/\/ \u0421\u0443\u0442\u044c \u0444\u043e\u0440\u043c\u0443\u043b\u044b - \u0432\u0435\u0440\u043d\u0443\u0442\u044c \u0431\u043e\u043b\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 `pos`, \/\/ \u043a\u043e\u0433\u0434\u0430 \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u043b\u0438\u0436\u0435 \u043a `arr[hi]`, \u0438 \/\/ \u043c\u0435\u043d\u044c\u0448\u0435\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435, \u043a\u043e\u0433\u0434\u0430 \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442 \u0431\u043b\u0438\u0436\u0435 \u043a `arr[lo]` pos = lo + ((x - arr[lo]) * (hi - lo) \/ (arr[hi] - arr[Lo]))  arr[] - \u0438\u0441\u0445\u043e\u0434\u043d\u044b\u0439 \u043c\u0430\u0441\u0441\u0438\u0432 x - \u0446\u0435\u043b\u0435\u0432\u043e\u0435 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0435 lo - \u043d\u0430\u0447\u0430\u043b\u044c\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 `arr[]` hi - \u043a\u043e\u043d\u0435\u0447\u043d\u044b\u0439 \u0438\u043d\u0434\u0435\u043a\u0441 `arr[]`<\/code><\/pre>\n<p> <\/p>\n<p>\u0412 \u0441\u0440\u0435\u0434\u043d\u0435\u043c \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u0438\u0440\u0443\u044e\u0449\u0438\u0439 \u043f\u043e\u0438\u0441\u043a \u043f\u0440\u043e\u0438\u0437\u0432\u043e\u0434\u0438\u0442 <code>log(log(n))<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439, \u0433\u0434\u0435 <code>n<\/code> \u2014 \u044d\u0442\u043e \u0447\u0438\u0441\u043b\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u0438\u0441\u0445\u043e\u0434\u043d\u043e\u0433\u043e \u043c\u0430\u0441\u0441\u0438\u0432\u0430. \u0427\u0438\u0441\u043b\u043e \u043d\u0435\u043e\u0431\u0445\u043e\u0434\u0438\u043c\u044b\u0445 \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439 \u0437\u0430\u0432\u0438\u0441\u0438\u0442 \u043e\u0442 \u0440\u0430\u0432\u043d\u043e\u043c\u0435\u0440\u043d\u043e\u0441\u0442\u0438 \u0440\u0430\u0441\u043f\u0440\u0435\u0434\u0435\u043b\u0435\u043d\u0438\u044f \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u0439 \u0441\u0440\u0435\u0434\u0438 \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432. \u0412 \u0445\u0443\u0434\u0448\u0435\u043c \u0441\u043b\u0443\u0447\u0430\u0435 (\u043d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u043a\u043e\u0433\u0434\u0430 \u0437\u043d\u0430\u0447\u0435\u043d\u0438\u044f \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u043e\u0432 \u044d\u043a\u0441\u043f\u043e\u043d\u0435\u043d\u0446\u0438\u0430\u043b\u044c\u043d\u043e \u0432\u043e\u0437\u0440\u0430\u0441\u0442\u0430\u044e\u0442) \u0438\u043d\u0442\u0435\u0440\u043f\u043e\u043b\u044f\u0446\u0438\u043e\u043d\u043d\u044b\u0439 \u043f\u043e\u0438\u0441\u043a \u043c\u043e\u0436\u0435\u0442 \u043f\u043e\u0442\u0440\u0435\u0431\u043e\u0432\u0430\u0442\u044c \u0434\u043e <code>O(n)<\/code> \u043e\u043f\u0435\u0440\u0430\u0446\u0438\u0439.<\/p>\n<p> <\/p>\n<p><strong>\u0420\u0435\u0430\u043b\u0438\u0437\u0430\u0446\u0438\u044f<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/interpolation-search.js export default function interpolationSearch(sortedArr, target) {   let start = 0   let end = sortedArr.length - 1    while (start &lt;= end) {     const rangeDelta = sortedArr[end] - sortedArr[start]     const indexDelta = end - start     const valueDelta = target - sortedArr[start]      \/\/ \u0415\u0441\u043b\u0438 `valueDelta` \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f `0`, \u0437\u043d\u0430\u0447\u0438\u0442, \u0438\u0441\u043a\u043e\u043c\u044b\u0439 \u044d\u043b\u0435\u043c\u0435\u043d\u0442     \/\/ \u0432 \u043c\u0430\u0441\u0441\u0438\u0432\u0435 \u043e\u0442\u0441\u0443\u0442\u0441\u0442\u0432\u0443\u0435\u0442     if (valueDelta &lt; 0) return -1      \/\/ \u0415\u0441\u043b\u0438 `rangeDelta` \u0440\u0430\u0432\u043d\u044f\u0435\u0442\u0441\u044f `0`, \u0437\u043d\u0430\u0447\u0438\u0442, \u043f\u043e\u0434\u043c\u0430\u0441\u0441\u0438\u0432 \u0441\u043e\u0434\u0435\u0440\u0436\u0438\u0442     \/\/ \u043e\u0434\u0438\u043d\u0430\u043a\u043e\u0432\u044b\u0435 \u0447\u0438\u0441\u043b\u0430, \u043f\u043e\u044d\u0442\u043e\u043c\u0443 \u0438\u0441\u043a\u0430\u0442\u044c \u043d\u0435\u0447\u0435\u0433\u043e     if (!rangeDelta) {       \/\/ \u042d\u0442\u043e \u0442\u0430\u043a\u0436\u0435 \u043f\u043e\u0437\u0432\u043e\u043b\u044f\u0435\u0442 \u0438\u0437\u0431\u0435\u0436\u0430\u0442\u044c \u0434\u0435\u043b\u0435\u043d\u0438\u044f \u043d\u0430 0 \u043f\u0440\u0438 \u043f\u043e\u0438\u0441\u043a\u0435       \/\/ \u0446\u0435\u043d\u0442\u0440\u0430\u043b\u044c\u043d\u043e\u0433\u043e \u044d\u043b\u0435\u043c\u0435\u043d\u0442\u0430 \u043d\u0438\u0436\u0435       return sortedArr[start] === target ? start : -1     }      const middleIndex =       start + Math.floor((valueDelta * indexDelta) \/ rangeDelta)      if (sortedArr[middleIndex] === target) {       return middleIndex     }      if (sortedArr[middleIndex] &lt; target) {       \/\/ \u041f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043f\u0440\u0430\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430       start = middleIndex + 1     } else {       \/\/ \u043f\u0435\u0440\u0435\u0445\u043e\u0434\u0438\u043c \u043a \u043b\u0435\u0432\u043e\u0439 \u043f\u043e\u043b\u043e\u0432\u0438\u043d\u0435 \u043c\u0430\u0441\u0441\u0438\u0432\u0430       end = middleIndex - 1     }   }    return -1 }<\/code><\/pre>\n<p> <\/p>\n<p><strong>\u0422\u0435\u0441\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u0438\u0435<\/strong><\/p>\n<p> <\/p>\n<pre><code class=\"javascript\">\/\/ algorithms\/searches\/__tests\/interpolation-search.test.js import interpolationSearch from '..\/interpolation-search'  describe('interpolationSearch', () =&gt; {   it('\u0434\u043e\u043b\u0436\u0435\u043d \u043d\u0430\u0439\u0442\u0438 \u0447\u0438\u0441\u043b\u0430 \u0432 \u043e\u0442\u0441\u043e\u0440\u0442\u0438\u0440\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u043c\u0430\u0441\u0441\u0438\u0432\u0430\u0445', () =&gt; {     expect(interpolationSearch([], 1)).toBe(-1)     expect(interpolationSearch([1], 1)).toBe(0)     expect(interpolationSearch([1], 0)).toBe(-1)     expect(interpolationSearch([1, 1], 1)).toBe(0)     expect(interpolationSearch([1, 2], 1)).toBe(0)     expect(interpolationSearch([1, 2], 2)).toBe(1)     expect(interpolationSearch([10, 20, 30, 40, 50], 40)).toBe(3)     expect(       interpolationSearch(         [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],         14,       ),     ).toBe(13)     expect(       interpolationSearch(         [1, 6, 7, 8, 12, 13, 14, 19, 21, 23, 24, 24, 24, 300],         24,       ),     ).toBe(10)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 600),     ).toBe(-1)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 1),     ).toBe(0)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 2),     ).toBe(1)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 3),     ).toBe(2)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 700),     ).toBe(3)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 800),     ).toBe(4)     expect(       interpolationSearch([0, 2, 3, 700, 800, 1200, 1300, 1400, 1900], 1200),     ).toBe(5)     expect(       interpolationSearch([1, 2, 3, 700, 800, 1200, 1300, 1400, 19000], 800),     ).toBe(4)     expect(interpolationSearch([0, 10, 11, 12, 13, 14, 15], 10)).toBe(1)   }) })<\/code><\/pre>\n<p> <\/p>\n<p>\u0417\u0430\u043f\u0443\u0441\u043a\u0430\u0435\u043c \u0442\u0435\u0441\u0442\u044b:<\/p>\n<p> <\/p>\n<pre><code class=\"bash\">npm run test .\/algorithms\/searches\/__tests__\/interpolation-search<\/code><\/pre>\n<p> <\/p>\n<p>\u0420\u0435\u0437\u0443\u043b\u044c\u0442\u0430\u0442:<\/p>\n<p> <img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/1y\/8k\/9f\/1y8k9fi_xr4ad5sudgqcgcal7d4.png\" data-src=\"https:\/\/habrastorage.org\/webt\/1y\/8k\/9f\/1y8k9fi_xr4ad5sudgqcgcal7d4.png\"\/> <\/p>\n<p> <\/p>\n<p> <\/p>\n<p>\u041d\u0430 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u044d\u0442\u043e \u0432\u0441\u0435, \u0434\u0440\u0443\u0437\u044c\u044f. \u0423\u0432\u0438\u0434\u0438\u043c\u0441\u044f \u0432 \u0441\u043b\u0435\u0434\u0443\u044e\u0449\u0435\u0439 \u0447\u0430\u0441\u0442\u0438.<\/p>\n<p> <\/p>\n<hr\/>\n<p> <\/p>\n<blockquote><p><a href=\"https:\/\/t.me\/timewebru\"><b>\u041d\u043e\u0432\u043e\u0441\u0442\u0438, \u043e\u0431\u0437\u043e\u0440\u044b \u043f\u0440\u043e\u0434\u0443\u043a\u0442\u043e\u0432 \u0438 \u043a\u043e\u043d\u043a\u0443\u0440\u0441\u044b \u043e\u0442 \u043a\u043e\u043c\u0430\u043d\u0434\u044b Timeweb.Cloud \u2014 \u0432 \u043d\u0430\u0448\u0435\u043c Telegram-\u043a\u0430\u043d\u0430\u043b\u0435<\/b><\/a> <b>\u21a9<\/b><\/p><\/blockquote>\n<p><a href=\"https:\/\/timeweb.cloud\/?i=106909\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w1560\/webt\/u9\/vg\/io\/u9vgio3hxj12h5u7j3un0wx_zpk.png\" data-src=\"https:\/\/habrastorage.org\/webt\/u9\/vg\/io\/u9vgio3hxj12h5u7j3un0wx_zpk.png\"\/><\/a><\/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\/856046\/\"> https:\/\/habr.com\/ru\/articles\/856046\/<\/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-1\">\n<div xmlns=\"http:\/\/www.w3.org\/1999\/xhtml\"><img decoding=\"async\" src=\"https:\/\/habrastorage.org\/r\/w780q1\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-src=\"https:\/\/habrastorage.org\/webt\/ma\/po\/lv\/mapolvqq4uunxfqoaviv3g9km9y.jpeg\" data-blurred=\"true\"\/> <\/p>\n<p> \u041f\u0440\u0438\u0432\u0435\u0442, \u0434\u0440\u0443\u0437\u044c\u044f!<\/p>\n<p> <\/p>\n<p>\u0412 \u044d\u0442\u043e\u0439 \u0441\u0435\u0440\u0438\u0438 \u0441\u0442\u0430\u0442\u0435\u0439 \u043c\u044b \u0440\u0430\u0437\u0431\u0438\u0440\u0430\u0435\u043c \u0441\u0442\u0440\u0443\u043a\u0442\u0443\u0440\u044b \u0434\u0430\u043d\u043d\u044b\u0445 \u0438 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u044b, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0435 \u0432 <a href=\"https:\/\/github.com\/trekhleb\/javascript-algorithms\">\u044d\u0442\u043e\u043c \u0437\u0430\u043c\u0435\u0447\u0430\u0442\u0435\u043b\u044c\u043d\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>. \u042d\u0442\u043e \u0441\u0435\u0434\u044c\u043c\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u0441\u0435\u0440\u0438\u0438.<\/p>\n<p> <\/p>\n<p>\u0421\u0435\u0433\u043e\u0434\u043d\u044f \u043c\u044b \u043f\u043e\u0433\u043e\u0432\u043e\u0440\u0438\u043c \u043e\u0431 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u0445 \u0434\u043b\u044f \u0440\u0430\u0431\u043e\u0442\u044b \u0441\u043e \u0441\u0442\u0440\u043e\u043a\u0430\u043c\u0438 \u0438 \u043f\u043e\u0438\u0441\u043a\u0430.<\/p>\n<p> <\/p>\n<p>\u041a\u043e\u0434, \u043f\u0440\u0435\u0434\u0441\u0442\u0430\u0432\u043b\u0435\u043d\u043d\u044b\u0439 \u0432 \u044d\u0442\u043e\u0439 \u0438 \u0434\u0440\u0443\u0433\u0438\u0445 \u0441\u0442\u0430\u0442\u044c\u044f\u0445 \u0441\u0435\u0440\u0438\u0438, \u043c\u043e\u0436\u043d\u043e \u043d\u0430\u0439\u0442\u0438 \u0432 <a href=\"https:\/\/github.com\/harryheman\/algorithms-data-structures\">\u044d\u0442\u043e\u043c \u0440\u0435\u043f\u043e\u0437\u0438\u0442\u043e\u0440\u0438\u0438<\/a>.<\/p>\n<p> <\/p>\n<p>\u0418\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u043e? \u0422\u043e\u0433\u0434\u0430 \u043f\u0440\u043e\u0448\u0443 \u043f\u043e\u0434 \u043a\u0430\u0442.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[],"tags":[],"class_list":["post-443175","post","type-post","status-publish","format-standard","hentry"],"_links":{"self":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/443175","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=443175"}],"version-history":[{"count":0,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=\/wp\/v2\/posts\/443175\/revisions"}],"wp:attachment":[{"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=443175"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=443175"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/savepearlharbor.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=443175"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}