ABB

題意：

長度為n的字符串，問最少添加多少字符可以使其構成回文字符串

題解：

最長回文字符串我的第一反應是manacher馬拉車算法，那我們直接馬拉車找到已有最長回文串，然后總長度減去不就是答案嗎？非也 ~ ~ 。注意是讓我們構造最長回文字符串，我們會發現，如果我們用馬拉車找到的最長回文串的最右端不是字符串最右端，那此情況就相當于作廢
比如：
murderforajarofz
我們可以找到最長回文串forajarof，但是最后一位z并不在里面，那你無論怎么構造也用不到forajarof這個回文串，也就是我們要找最長的帶最后一個字符的回文字符串
我們直接在manacher的基礎上改就可以，原本式子中的ans，我們每查找完一次清零，也就是如果找到的回文串不是帶尾的不要，如果帶尾保留最大值
詳細看代碼

代碼：

#include <bits/stdc++.h> using namespace std; const int maxn = 9*1e5+4; char s[maxn]; char str[maxn]; int p[maxn];//表示以i為中心的最長回文子串長度，int init() {int len = strlen(s);str[0] = '@', str[1] = '#';int j = 2;for (int i = 0; i < len; ++i) str[j++] = s[i], str[j++] = '#';str[j] = '\0'; // cout<<j<<endl;return j; } int manacher() {int len = init(),sum=-1; int mx = 0;//同時記錄一個當前延伸最遠的回文子串 int id = 0;//對稱中心 int ans = -1;for (int i = 1; i < len; ++i) {if (i < mx) p[i] = min(p[id * 2 - i], mx - i);else p[i] = 1;while (str[i + p[i]] == str[i - p[i]]) p[i]++;//if(i+p[i]==len-1) if (p[i] + i > mx) mx = p[i] + i, id = i;// cout<<"id="<<id<<endl;ans = max(ans, p[i] - 1);if(mx==len)sum=max(sum,ans);//cout<<"ans="<<ans<<endl;//cout<<"mx="<<mx<<endl;//cout<<"sum="<<sum<<endl;ans=0;}return sum; } int main() {int t;cin>>t;for(int i=0;i<t;i++)cin>>s[i];if(manacher()==0)cout<<t-1<<endl;else cout <<t-manacher()<<endl;return 0; }

總結

以上是生活随笔為你收集整理的ABB (2020牛客国庆集训派对day1)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。