{"id":1640,"date":"2021-08-29T21:27:19","date_gmt":"2021-08-30T04:27:19","guid":{"rendered":"http:\/\/66.94.114.210\/?p=1640"},"modified":"2021-08-29T21:29:38","modified_gmt":"2021-08-30T04:29:38","slug":"the-manacher-algorithm-template","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/08\/29\/the-manacher-algorithm-template\/","title":{"rendered":"The Manacher&#8217;s Algorithm Template"},"content":{"rendered":"\n<p>The Manacher algorithm is a linear algorithm to calculate the total number of palindromic substring of the given string (also the longest <meta charset=\"utf-8\">palindromic substring). The problem has other solutions, including <code>O(n^2)<\/code> dynamic programming and <code>O(nlogn)<\/code> rolling hash + binary search result.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp line-numbers\">\/\/ for each position i=0\u2026n\u22121 we'll find the values d1[i] and d2[i], denoting the number of palindromes \n\/\/ accordingly with odd and even lengths with centers in the position i.\n\n\/\/ For instance, string s=abababc has three palindromes with odd length with centers in the position s[3]=b, i. e. d1[3]=3:\n\/\/ a b a b a b \n\/\/       _\n\/\/     _ _ _\n\/\/   _ _ _ _ _\n\n\/\/ And string s=cbaabd has two palindromes with even length with centers in the position s[3]=a, i. e. d2[3]=2:\n\/\/ c b a a b d\n\/\/     _ _\n\/\/   _ _ _ _\n\n\nvector&lt;int&gt; GetD1(string_view s) {\n  int n = s.size();\n  vector&lt;int&gt; d1(n);\n  for (int i = 0, l = 0, r = -1; i &lt; n; i++) {\n    int k = (i &gt; r) ? 1 : min(d1[l + r - i], r - i + 1);\n    while (0 &lt;= i - k &amp;&amp; i + k &lt; n &amp;&amp; s[i - k] == s[i + k]) {\n      k++;\n    }\n    d1[i] = k--;\n    if (i + k &gt; r) {\n      l = i - k;\n      r = i + k;\n    }\n  }\n  return d1;\n}\n\nvector&lt;int&gt; GetD2(string_view s) {\n  int n = s.size();\n  vector&lt;int&gt; d2(n);\n  for (int i = 0, l = 0, r = -1; i &lt; n; i++) {\n    int k = (i &gt; r) ? 0 : min(d2[l + r - i + 1], r - i + 1);\n    while (0 &lt;= i - k - 1 &amp;&amp; i + k &lt; n &amp;&amp; s[i - k - 1] == s[i + k]) {\n      k++;\n    }\n    d2[i] = k--;\n    if (i + k &gt; r) {\n      l = i - k - 1;\n      r = i + k ;\n    }\n  }\n  return d2;\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Reference<\/h2>\n\n\n\n<p>https:\/\/cp-algorithms.com\/string\/manacher.html<a href=\"\"><\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Manacher algorithm is a linear algorithm to calculate the total number of palindromic substring of the given string (also the longest palindromic substring). The problem has other solutions, including O(n^2) dynamic programming and O(nlogn) rolling hash + binary search result. Reference https:\/\/cp-algorithms.com\/string\/manacher.html<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,69],"tags":[],"class_list":["post-1640","post","type-post","status-publish","format-standard","hentry","category-alg","category-manacher"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1640","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1640"}],"version-history":[{"count":4,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1640\/revisions"}],"predecessor-version":[{"id":1645,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1640\/revisions\/1645"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1640"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1640"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1640"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}