{"id":50,"date":"2022-04-11T02:40:57","date_gmt":"2022-04-10T18:40:57","guid":{"rendered":"http:\/\/120.55.184.7\/?p=50"},"modified":"2025-04-27T18:16:03","modified_gmt":"2025-04-27T10:16:03","slug":"%e6%9c%80%e9%95%bf%e5%9b%9e%e6%96%87%e5%ad%90%e4%b8%b2","status":"publish","type":"post","link":"https:\/\/beijian99.top\/?p=50","title":{"rendered":"\u6700\u957f\u56de\u6587\u5b50\u4e32"},"content":{"rendered":"\n<p>\u9a6c\u62c9\u8f66\u7b97\u6cd5\uff08Manacher&#8217;s Algorithm\uff09\u662f\u7528\u4e8e\u9ad8\u6548\u67e5\u627e\u5b57\u7b26\u4e32\u4e2d\u6700\u957f\u56de\u6587\u5b50\u4e32\u7684\u7b97\u6cd5\u3002\u5176\u6838\u5fc3\u5728\u4e8e\u901a\u8fc7\u5bf9\u79f0\u6027\u548c\u9884\u5904\u7406\uff0c\u5c06\u5bfb\u627e\u6700\u957f\u56de\u6587\u5b50\u4e32\u7684\u65f6\u95f4\u590d\u6742\u5ea6\u4f18\u5316\u5230 O(n)\u3002\u4ee5\u4e0b\u662f\u8be6\u7ec6\u539f\u7406\u548c\u793a\u4f8b\u89e3\u6790\uff1a<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u4e00\u3001\u6838\u5fc3\u601d\u60f3<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u56de\u6587\u7684\u6027\u8d28<br>\u56de\u6587\u4e2d\u5fc3\u5bf9\u79f0\uff0c\u4f46\u5b58\u5728\u4e24\u79cd\u7c7b\u578b\uff1a<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5947\u6570\u957f\u5ea6\uff1a\u5982 <code>\"aba\"<\/code>\uff0c\u4e2d\u5fc3\u4e3a\u5355\u4e2a\u5b57\u7b26 <code>'b'<\/code>\u3002<\/li>\n\n\n\n<li>\u5076\u6570\u957f\u5ea6\uff1a\u5982 <code>\"abba\"<\/code>\uff0c\u4e2d\u5fc3\u5728\u4e24\u4e2a\u5b57\u7b26 <code>'b'<\/code> \u4e4b\u95f4\u3002<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u9884\u5904\u7406\uff1a\u7edf\u4e00\u5947\u5076\u957f\u5ea6<br>\u4e3a\u4e86\u7edf\u4e00\u5904\u7406\uff0c\u5728\u539f\u59cb\u5b57\u7b26\u4e32\u7684\u6bcf\u4e2a\u5b57\u7b26\u95f4\u63d2\u5165\u7279\u6b8a\u5b57\u7b26\uff08\u5982 <code>#<\/code>\uff09\uff0c\u5e76\u5728\u9996\u5c3e\u6dfb\u52a0\u4e0d\u540c\u5b57\u7b26\uff08\u5982 <code>^<\/code> \u548c <code>$<\/code>\uff09\u907f\u514d\u8fb9\u754c\u68c0\u67e5\u3002<br>\u793a\u4f8b\uff1a<br>\u539f\u59cb\u5b57\u7b26\u4e32 <code>\"babad\"<\/code> \u2192 \u9884\u5904\u7406\u540e <code>\"^#b#a#b#a#d#$\"<\/code><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u5947\u6570\u957f\u5ea6\u56de\u6587\u53d8\u4e3a\u4ee5 <code>#<\/code> \u4e3a\u4e2d\u5fc3\uff0c\u5076\u6570\u957f\u5ea6\u56de\u6587\u53d8\u4e3a\u4ee5\u539f\u5b57\u7b26\u4e3a\u4e2d\u5fc3\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u4e8c\u3001\u5173\u952e\u6b65\u9aa4<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u5b9a\u4e49\u6570\u7ec4 <code>len[]<\/code><\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>len[i]<\/code> \u8868\u793a\u4ee5\u9884\u5904\u7406\u5b57\u7b26\u4e32\u4e2d\u7b2c <code>i<\/code> \u4e2a\u5b57\u7b26\u4e3a\u4e2d\u5fc3\u7684\u6700\u957f\u56de\u6587\u534a\u5f84\uff08\u5305\u542b\u81ea\u8eab\uff09\u3002<\/li>\n\n\n\n<li>\u5b9e\u9645\u56de\u6587\u957f\u5ea6 = <code>len[i] - 1<\/code>\uff08\u4f8b\u5982\uff0c<code>len[i]=4<\/code> \u5bf9\u5e94\u957f\u5ea6\u4e3a <code>3<\/code> \u7684\u56de\u6587\uff09\u3002<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u7ef4\u62a4\u5bf9\u79f0\u6027<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u7528 <code>center<\/code> \u548c <code>right<\/code> \u8bb0\u5f55\u5f53\u524d\u5df2\u77e5\u7684\u6700\u53f3\u56de\u6587\u5b50\u4e32\u7684\u4e2d\u5fc3\u548c\u53f3\u8fb9\u754c\u3002<\/li>\n\n\n\n<li>\u5f53\u5904\u7406\u4f4d\u7f6e <code>i<\/code> \u65f6\uff0c\u82e5 <code>i<\/code> \u5728 <code>right<\/code> \u5de6\u4fa7\uff0c\u53ef\u5229\u7528\u5bf9\u79f0\u70b9 <code>mirror = 2*center - i<\/code> \u7684\u4fe1\u606f\u5feb\u901f\u521d\u59cb\u5316 <code>len[i]<\/code>\u3002<\/li>\n<\/ul>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u4e2d\u5fc3\u6269\u5c55<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u4ece <code>i<\/code> \u5411\u4e24\u4fa7\u6269\u5c55\uff0c\u76f4\u5230\u65e0\u6cd5\u5339\u914d\uff0c\u66f4\u65b0 <code>len[i]<\/code>\u3002<\/li>\n\n\n\n<li>\u82e5\u6269\u5c55\u540e\u7684\u53f3\u8fb9\u754c\u8d85\u8fc7 <code>right<\/code>\uff0c\u5219\u66f4\u65b0 <code>center<\/code> \u548c <code>right<\/code>\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u4e09\u3001\u793a\u4f8b\u89e3\u6790\uff1a\u4ee5 <code>\"babad\"<\/code> \u4e3a\u4f8b<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u9884\u5904\u7406\u5b57\u7b26\u4e32<br>\u539f\u59cb\u5b57\u7b26\u4e32\uff1a<code>b a b a d<\/code><br>\u9884\u5904\u7406\u540e\uff1a<code>^ # b # a # b # a # d #$<\/code><br>\u7d22\u5f15\uff1a<code>0 1 2 3 4 5 6 7 8 9 10 11<\/code><\/li>\n\n\n\n<li>\u8ba1\u7b97 <code>len[]<\/code> \u6570\u7ec4<br>\u904d\u5386\u6bcf\u4e2a\u4f4d\u7f6e <code>i<\/code>\uff0c\u5229\u7528\u5bf9\u79f0\u6027\u548c\u6269\u5c55\u89c4\u5219\uff1a<\/li>\n<\/ol>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>\u6b65\u9aa4<\/th><th>i<\/th><th>\u955c\u50cf mirror<\/th><th>\u521d\u59cb len[i]<\/th><th>\u6269\u5c55\u540e len[i]<\/th><th>\u8bf4\u660e<\/th><\/tr><\/thead><tbody><tr><td>1<\/td><td>1<\/td><td>&#8211;<\/td><td>0<\/td><td>0<\/td><td>\u8fb9\u754c <code>#<\/code>\uff0c\u65e0\u6cd5\u6269\u5c55<\/td><\/tr><tr><td>2<\/td><td>2<\/td><td>0<\/td><td>min(0, \u2026)<\/td><td>1 \u2192 \u6269\u5c55\u5230 <code>b#b<\/code> \u2192 <code>len[2]=3<\/code><\/td><td>\u4e2d\u5fc3\u6269\u5c55\u540e\uff0c<code>i+len[i]=5<\/code> \u8d85\u8fc7\u5f53\u524d <code>right=2<\/code>\uff0c\u66f4\u65b0 <code>center=2<\/code>, <code>right=5<\/code><\/td><\/tr><tr><td>3<\/td><td>3<\/td><td>1<\/td><td>0<\/td><td>0 \u2192 \u65e0\u6cd5\u6269\u5c55<\/td><td><\/td><\/tr><tr><td>4<\/td><td>4<\/td><td>2<\/td><td>min(5-4=1, len[2]=3) \u2192 1<\/td><td>\u6269\u5c55\u5230 <code>a#b#a<\/code> \u2192 <code>len[4]=4<\/code><\/td><td>\u66f4\u65b0 <code>center=4<\/code>, <code>right=8<\/code><\/td><\/tr><tr><td>5<\/td><td>5<\/td><td>3<\/td><td>0<\/td><td>0 \u2192 \u65e0\u6cd5\u6269\u5c55<\/td><td><\/td><\/tr><tr><td>6<\/td><td>6<\/td><td>4<\/td><td>min(8-6=2, len[4]=4) \u2192 2<\/td><td>\u6269\u5c55\u5230 <code>b#a#b<\/code> \u2192 <code>len[6]=4<\/code><\/td><td><code>i+len[i]=10<\/code> \u672a\u8d85 <code>right=8<\/code>\uff0c\u4e0d\u66f4\u65b0 <code>center<\/code><\/td><\/tr><tr><td>7<\/td><td>7<\/td><td>5<\/td><td>0<\/td><td>0 \u2192 \u65e0\u6cd5\u6269\u5c55<\/td><td><\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<ol start=\"3\" class=\"wp-block-list\">\n<li>\u7ed3\u679c\u63d0\u53d6<\/li>\n<\/ol>\n\n\n\n<ul class=\"wp-block-list\">\n<li>\u6700\u5927 <code>len[i]<\/code> \u4e3a <code>4<\/code>\uff08\u4f4d\u7f6e <code>i=4<\/code> \u548c <code>i=6<\/code>\uff09\u3002<\/li>\n\n\n\n<li>\u6700\u957f\u56de\u6587\u5b50\u4e32\u957f\u5ea6 = <code>4 - 1 = 3<\/code>\u3002<\/li>\n\n\n\n<li>\u8d77\u59cb\u4f4d\u7f6e\uff1a<code>(i - len[i]) \/ 2 = (4-4)\/2 = 0<\/code> \u2192 \u539f\u5b57\u7b26\u4e32\u7684 <code>\"bab\"<\/code> \u6216 <code>(6-4)\/2=1<\/code> \u2192 <code>\"aba\"<\/code>\u3002<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u56db\u3001\u7b97\u6cd5\u4f18\u52bf<\/strong><\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li>\u7ebf\u6027\u65f6\u95f4\u590d\u6742\u5ea6\uff1a\u6bcf\u4e2a\u5b57\u7b26\u6700\u591a\u88ab\u8bbf\u95ee\u4e24\u6b21\uff08\u6269\u5c55\u548c\u5bf9\u79f0\u6027\u5229\u7528\uff09\u3002<\/li>\n\n\n\n<li>\u7edf\u4e00\u5904\u7406\u5947\u5076\u957f\u5ea6\uff1a\u901a\u8fc7\u9884\u5904\u7406\u7b80\u5316\u903b\u8f91\u3002<\/li>\n\n\n\n<li>\u907f\u514d\u91cd\u590d\u8ba1\u7b97\uff1a\u5229\u7528\u5bf9\u79f0\u6027\u51cf\u5c11\u6269\u5c55\u6b21\u6570\u3002<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u4e94\u3001\u5173\u952e\u4ee3\u7801\u903b\u8f91\uff08C++\uff09<\/strong><\/p>\n\n\n<div class=\"wp-block-syntaxhighlighter-code \"><pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\nstring longestPalindrome(string s) {\n    string t = preprocess(s); \/\/ \u9884\u5904\u7406\n    int n = t.size();\n    vector&lt;int&gt; len(n, 0);\n    int center = 0, right = 0;\n    int max_len = 0, max_center = 0;\n\n    for (int i = 1; i &lt; n - 1; i++) {\n        int mirror = 2 * center - i;\n\n        \/\/ \u5229\u7528\u5bf9\u79f0\u6027\u521d\u59cb\u5316 len&#x5B;i]\n        if (i &lt; right)\n            len&#x5B;i] = min(right - i, len&#x5B;mirror]);\n\n        \/\/ \u4e2d\u5fc3\u6269\u5c55\n        while (t&#x5B;i + len&#x5B;i] + 1] == t&#x5B;i - len&#x5B;i] - 1])\n            len&#x5B;i]++;\n\n        \/\/ \u66f4\u65b0\u6700\u53f3\u8fb9\u754c\u548c\u4e2d\u5fc3\n        if (i + len&#x5B;i] &gt; right) {\n            center = i;\n            right = i + len&#x5B;i];\n        }\n\n        \/\/ \u66f4\u65b0\u6700\u5927\u503c\n        if (len&#x5B;i] &gt; max_len) {\n            max_len = len&#x5B;i];\n            max_center = i;\n        }\n    }\n\n    \/\/ \u8f6c\u6362\u4e3a\u539f\u5b57\u7b26\u4e32\u7684\u8d77\u59cb\u4f4d\u7f6e\n    int start = (max_center - max_len) \/ 2;\n    return s.substr(start, max_len);\n}\n<\/pre><\/div>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><strong>\u516d\u3001\u603b\u7ed3<\/strong><br>\u9a6c\u62c9\u8f66\u7b97\u6cd5\u901a\u8fc7\u9884\u5904\u7406\u7edf\u4e00\u5947\u5076\u56de\u6587\uff0c\u5e76\u5229\u7528\u5bf9\u79f0\u6027\u4f18\u5316\u8ba1\u7b97\uff0c\u9ad8\u6548\u627e\u5230\u6700\u957f\u56de\u6587\u5b50\u4e32\u3002\u5176\u6838\u5fc3\u5728\u4e8e\u7ef4\u62a4 <code>len[]<\/code> \u6570\u7ec4\u548c\u52a8\u6001\u8c03\u6574 <code>center<\/code> \u4e0e <code>right<\/code>\uff0c\u786e\u4fdd\u6bcf\u4e2a\u5b57\u7b26\u4ec5\u88ab\u8bbf\u95ee\u5e38\u6570\u6b21\uff0c\u6700\u7ec8\u8fbe\u5230 O(n) \u7684\u65f6\u95f4\u590d\u6742\u5ea6\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9a6c\u62c9\u8f66\u7b97\u6cd5\uff08Manacher&#8217;s Algorithm\uff09\u662f\u7528\u4e8e\u9ad8\u6548\u67e5\u627e\u5b57\u7b26\u4e32\u4e2d\u6700\u957f\u56de\u6587\u5b50\u4e32\u7684\u7b97\u6cd5\u3002\u5176 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":392,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"footnotes":""},"categories":[4],"tags":[],"class_list":["post-50","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithm"],"_links":{"self":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/50","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=50"}],"version-history":[{"count":10,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/50\/revisions"}],"predecessor-version":[{"id":807,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/posts\/50\/revisions\/807"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=\/wp\/v2\/media\/392"}],"wp:attachment":[{"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=50"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=50"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/beijian99.top\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=50"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}