題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)字符串，求字符串中最長(zhǎng)的回文子串，這個(gè)字串可以包含主串本身

題目分析：這個(gè)題就是之前徐州網(wǎng)絡(luò)賽的那個(gè)回文題目的弱化版。。那個(gè)題目正解是要用回文自動(dòng)機(jī)，但我不會(huì)，當(dāng)時(shí)搞了兩天終于還是用哈希+二分+動(dòng)態(tài)規(guī)劃亂搞出來(lái)了，這個(gè)題目的話更直接，直接問(wèn)了最長(zhǎng)的回文子串的長(zhǎng)度，所以連動(dòng)態(tài)規(guī)劃也用不到了，直接把上次那個(gè)題目的套路搬過(guò)來(lái)就行了

處理回文串用馬拉車算法比較好，但我不會(huì)，也沒(méi)必要學(xué)了，用二分和哈希，分情況亂搞一下就出來(lái)了（太懶了orz

還有回文自動(dòng)機(jī)也是，現(xiàn)在一個(gè)自動(dòng)機(jī)也不會(huì)，下午打算去學(xué)學(xué)AC自動(dòng)機(jī)，好像是最簡(jiǎn)單的自動(dòng)機(jī)了?

---

?2019.11.10更新：

學(xué)會(huì)了馬拉車來(lái)回顧一下這給題目，不得不被馬拉車的精妙設(shè)計(jì)和時(shí)間復(fù)雜度所驚艷，比二分和哈希的時(shí)間復(fù)雜度小了5倍還要多，而且代碼寫起來(lái)也簡(jiǎn)單多了，在下面貼一下代碼

代碼：

二分+哈希

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef unsigned long long ull;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;string s;int n;ull hash1[N],hash2[N];ull f[N];void Hash() {hash1[0]=hash2[n+1]=0;f[0]=1;for(int i=1;i<=n;i++){hash1[i]=hash1[i-1]*131+s[i]-'a';f[i]=f[i-1]*131;}for(int i=n;i>=1;i--)hash2[i]=hash2[i+1]*131+s[i]-'a'; }ull gethash1(int l,int r) {return hash1[r]-hash1[l-1]*f[r-l+1]; }ull gethash2(int l,int r) {return hash2[l]-hash2[r+1]*f[r-l+1]; }bool check(int pos,int len,bool state) {int l,r;if(state)//odd{l=pos-len;r=pos+len;}else//even{l=pos-len;r=pos+len+1;}if(l<=0||r>n)return false;ull a=gethash1(l,r);ull b=gethash2(l,r);return a==b; }int main() { // freopen("input.txt","r",stdin);int kase=0;while(cin>>s&&s!="END"){n=s.size();s=" "+s;Hash();int ans=0;for(int i=1;i<=n;i++)//odd{int l=0,r=n;int len=0;while(l<=r){int mid=l+r>>1;if(check(i,mid,true)){len=mid;l=mid+1;}elser=mid-1;}ans=max(ans,2*len+1);}for(int i=1;i<n;i++)//even{int l=0,r=n;int len=0;while(l<=r){int mid=l+r>>1;if(check(i,mid,false)){len=mid;l=mid+1;}elser=mid-1;}ans=max(ans,2*(len+1));}printf("Case %d: %d\n",++kase,ans);}return 0; }

馬拉車：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;char s[N*2];char str[N*2];int p[N*2];int Manacher() {int k=0;s[k++]='!';for(int i=0;str[i];i++){s[k++]='#';s[k++]=str[i];}s[k++]='#';s[k]=0;int ans=0;p[0]=1;int id=0,mmax=0;for(int i=1;i<k;i++){if(i<mmax)p[i]=min(mmax-i,p[2*id-i]);elsep[i]=1;while(s[i-p[i]]==s[i+p[i]])p[i]++;if(i+p[i]>mmax){mmax=i+p[i];id=i;}ans=max(ans,p[i]-1);}return ans; } int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);int kase=0;while(scanf("%s",str)!=EOF&&str[0]!='E')printf("Case %d: %d\n",++kase,Manacher());return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的POJ - 3974 Palindrome(二分+哈希/马拉车)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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