傳送門：Palindrome Reversion
標簽：字符串
題目大意
規定一個操作：選擇字符串中的一段區間[l,r]并使其翻轉。現在給出一個字符串s，你要判斷能否通過一次操作使其變為回文串。
輸入：一個字符串，其長度不超過1e5。
輸出：可以則輸出l和r，否則輸出"-1 -1"。
算法分析
- 題目的意思可以說是相當的簡單，但正所謂大道至簡，容易讀懂不代表容易做。我們先要知道回文串的特征：翻轉后與翻轉前完全相同（這里指的是整個字符串reverse）。那么我們可以大膽地猜測一個結論：原字符串首尾相同的部分必然不被包含在操作區間[l,r]中。因為如果有一部分在[l,r]之間，要想保證操作后整個串回文，就要讓替換這部分的字符與之相同，那么替換就毫無意義。
- 也就是說我們可以先通過遍歷找到第一個不滿足首尾相同的字符，假設其下標是i，這樣一來區間[l,r]要么包括i，要么包括len-i+1（這里len為字符串長度）。因為此時的字符串第一個字符和最后一個字符不同，所以需要換掉第一個或者最后一個字符來使得它們相同，但是又要想到同時替換并不會改變它們的對應關系。
- 所以現在問題變得簡單了起來，只要在去掉了首尾相同部分的新字符串上從前往后枚舉區間，再從后往前枚舉區間，并判斷翻轉后整體是否回文，就能得出方案的可行性。不過實現起來有點難度，因為要正反各處理一次哈希，還要用到哈希值的截取、拼接等操作，稍有不慎就會出bug。不過有一個小技巧能讓本題輕松一半，就是在正向枚舉完區間后將整個字符串翻轉，然后再次正向枚舉區間，這樣就和反向枚舉區間的作用是一樣的了。
- 最后還要特判一下原字符串本身就回文的情況，這時直接輸出1和len即可。只要推出了最初的結論，這題的思路就很簡單，難點主要在于實現。以上算法總體時間復雜度為預處理雙向哈希的復雜度，即O(n)。
代碼實現
#include <iostream>
using namespace std;
#include <algorithm>
#include <cstring>
long long len,hal[100005],har[100005],base[100005]={1LL};
const int mod=1e9+19;
const long long P=13031LL;
char str[100005],str1[100005];
void init(){int i;hal[0]=str[0];for(i=1;i<len;i++)hal[i]=(hal[i-1]*P+str[i])%mod;har[len-1]=str[len-1];for(i=len-2;i>=0;i--)har[i]=(har[i+1]*P+str[i])%mod;
}
long long getl(int l,int r){if(l>r)return 0;if(!l)return hal[r];return (hal[r]-1LL*hal[l-1]*base[r-l+1]%mod+mod)%mod;
}
long long getr(int l,int r){if(l>r)return 0;if(r==len-1)return har[l];return (har[l]-1LL*har[r+1]*base[r-l+1]%mod+mod)%mod;
}
int main(){int i,j,x,len1;bool flag=0;ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);for(i=1;i<=1e5;i++)base[i]=base[i-1]*P%mod;cin>>str1;len1=strlen(str1);for(j=0;j<len1&&str1[j]==str1[len1-j-1];j++);if(j==len1){cout<<1<<' '<<len1;return 0;}for(i=j;i<len1-j;i++)str[i-j]=str1[i];len=len1-2*j;init();x=len/2;for(i=0;i<len;i++)if(i<x){if(getr(x,len-1)==(getr(0,i)*base[x-1+(len&1)-i]%mod+getl(i+1,x-1+(len&1)))%mod){cout<<1+j<<' '<<i+1+j;return 0;}}else{if(getr(i-x+1,i)==(getl(0,i-x-(len&1))+getr(i+1,len-1)*base[i-x-(len&1)+1]%mod)%mod){cout<<1+j<<' '<<i+1+j;return 0;}}reverse(str,str+len);init();x=len/2;for(i=0;i<len;i++)if(i<x){if(getr(x,len-1)==(getr(0,i)*base[x-1+(len&1)-i]%mod+getl(i+1,x-1+(len&1)))%mod){cout<<len1-(i+1+j)+1<<' '<<len1-(1+j)+1;return 0;}}else{if(getr(i-x+1,i)==(getl(0,i-x-(len&1))+getr(i+1,len-1)*base[i-x-(len&1)+1]%mod)%mod){cout<<len1-(i+1+j)+1<<' '<<len1-(1+j)+1;return 0;}}cout<<-1<<' '<<-1;
}
)
