<\/p>\n
\u7b97\u6cd5\u4e00\uff1aManacher<\/p>\n
\r\n#define REP(i, n) for (int i=0;i<n;++i)\r\n#define FOR(i, a, b) for (int i=a;i<b;++i)\r\n#define DWN(i, b, a) for (int i=b-1;i>=a;--i)\r\nconst int N = int(2e5) + 9;\r\nchar s[N]; int r[N]; int n;\r\n\r\nclass Solution {\r\npublic:\r\n string shortestPalindrome(string ss) {\r\n int nn = ss.size(); \r\n \r\n n = 2*nn+2; s[0] = '$'; REP(i, nn) s[i*2+1]='.',s[i*2+2]=ss[i];s[n-1]='.'; s[n] = 0;\r\n\r\n int mx=0,mi=0;FOR(i,1,n){\r\n for (r[i]=mx>i?min(r[2*mi-i],mx-i):1;s[i+r[i]]==s[i-r[i]];++r[i]);\r\n if (i+r[i]>mx)mx=i+r[i],mi=i;\r\n }\r\n \r\n int rn = 0x3f3f3f3f; DWN(i,n,1) if (r[i] == i){\r\n rn = nn-i+1;\r\n break;\r\n }\r\n \r\n string rr = ss; reverse(rr.begin(), rr.end());\r\n return rr.substr(0, rn) + ss;\r\n }\r\n};\r\n<\/pre>\n\u7b97\u6cd5\u4e8c\uff1aKMP<\/p>\n
\r\n#define REP(i, n) for (int i=0;i<n;++i)\r\n#define FOR(i, a, b) for (int i=a;i<b;++i)\r\n#define DWN(i, b, a) for (int i=b-1;i>=a;--i)\r\nconst int N = int(2e5) + 9;\r\nint pi[N]; \r\n\r\nclass Solution {\r\npublic:\r\n string shortestPalindrome(string ss) {\r\n string rr = ss; int nn = ss.size();\r\n reverse(rr.begin(), rr.end());\r\n string s = ss + '$' + rr;\r\n int n = s.size(); for (int i = 1, j = pi[0] = -1; i < n; ++i){\r\n while (j >= 0 && s[i] != s[j+1]) j = pi[j];\r\n if (s[i] == s[j+1]) ++j;\r\n pi[i] = j;\r\n }\r\n return rr.substr(0, nn-1-pi[n-1]) + ss;\r\n }\r\n};\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[142],"tags":[],"class_list":["post-1139","post","type-post","status-publish","format-standard","hentry","category-leetcode"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-in","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1139","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=1139"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1139\/revisions"}],"predecessor-version":[{"id":1140,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1139\/revisions\/1140"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}