快速的求出一個字符串中最長的回文串的長度

https://www.luogu.com.cn/problem/P3805

#include <iostream> #include <cstring> #include <algorithm> using namespace std; char s[20000000+10]; char s_new[20000000+10]; int p[20000000+10];//p[i] 表示以 i 為中心的最長回文的半徑 //使用馬拉車之前需要對字符串進(jìn)行改造 int Init() {int len = strlen(s);s_new[0] = '$';s_new[1] = '#';int j = 2;for (int i = 0; i < len; i++){s_new[j++] = s[i];s_new[j++] = '#';}s_new[j++] = '^'; // 別忘了哦return j; // 返回 s_new 的長度 }int Manacher() {int len = Init(); // 取得新字符串長度并完成向 s_new 的轉(zhuǎn)換int max_len = -1; // 最長回文長度int id;//id為i和j的中心點(diǎn) i以 id 為對稱點(diǎn)翻折到j(luò)的位置int mx = 0;// mx 代表以 id 為中心的最長回文的右邊界for (int i = 1; i < len; i++){if (i < mx)//mx 代表以 id 為中心的最長回文的右邊界p[i] = min(p[2 * id - i], mx - i); // 2 * id - i 為 i 關(guān)于 id 的對稱點(diǎn)else p[i] = 1;//超過邊界總共就不是回文了while (s_new[i - p[i]] == s_new[i + p[i]]) // 不需邊界判斷，因?yàn)樽笥?$，右有 ^ 二者必不可能相等p[i]++;// 我們每走一步 i，都要和 mx 比較，我們希望 mx 盡可能的遠(yuǎn)，// 這樣才能更有機(jī)會執(zhí)行 if (i < mx)這句代碼，從而提高效率if (mx < i + p[i])//i的位置再加上i對應(yīng)的回文半徑即為最遠(yuǎn)的邊界{id = i;mx = i + p[i];}max_len = max(max_len, p[i] - 1);// p[i]-1 即為原字符串中最長回文串的長度}return max_len; }int main() {scanf("%s", s);cout<<Manacher()<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的P3805 【模板】manacher 算法【马拉车】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。