Time limit 2000 ms
Memory limit 32768 kB
给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等
回文就是正反读都是一样的字符串,如aba, abba等
Input输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000Output每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.
Sample Input
aaaa
abab
Sample Output
4
3
本題大意：
求一個字符串中的所有子串中是回文串的子串的最大長度。
解題思想：
hash，哈希是一個無腦暴力對付字符串極為有力的工具。其實就給字符串編號，就想人類的身份證號碼一樣，每個字符串有自己的ID，而這個ID就是通過hash來賦予。
有了hash這把利劍，接下來就是遍歷整個字符串，用二分的思想來枚舉回文子串的長度：例如當長度為奇數時、遍歷到了i點，先得出以i點為對稱中心的子串的長度，以i+1為左端點，
最大長度的地方為右端點，取中間為mid，這樣先判斷，（i+1到mid）、（i-1-mid到i-1），這兩段字符串是否回文，即看他們的hash值是否相同（這裡我們需要正序和逆序兩個哈希）
如果相同說明回文，那做左端點移到mid+1，這樣mid就會離i更遠的地方去繼續嘗試，如果不同，右端點就移到i-1。知道l>r時，r-i+1回文子串的長度。（下面的結合代碼理解）
我調試了近半個小時，一直在TLE，這裡需要注意一個點！scanf（"%s",s+1)前面要用“~”，否則EOF是不能讓while語句停下來的因為EOF也可以作為一個字符成功的讀到字符數組裡面去。
#include<bits/stdc++.h> #define N 110009 using namespace std; typedef unsigned long long ull; const int bas=27; char s[N]; ull lh[N],rh[N],p[N];//lh是從左邊開始的hash，rh是右邊的 int a,b,ans,len; int get(int maxl,int a,int b)//maxl是可取的最長子串 { int r=maxl,l=b; while(l<=r) //二分查找 { int mid=(l+r)/2; int temp=a-mid+b; int left=lh[mid]-lh[b-1]*p[mid-b+1]; int right=rh[temp]-rh[a+1]*p[mid-b+1]; if(left!=right) r=mid-1; else l=mid+1; } return r-b+1; } int main() { p[0]=1; for(int i=1;i<N;i++) p[i]=p[i-1]*bas; while(~scanf("%s",s+1)) //切記加上“~”否則EOF不能終止程序 { len=strlen(s+1); s[0]='#'; lh[0]=rh[len+1]=0; for(int i=1;i<=len;i++) { lh[i]=lh[i-1]*bas+s[i]-'a';//構造出lh數組 } for(int i=len;i>0;i--) { rh[i]=rh[i+1]*bas+s[i]-'a';//構造rh數組 } ans=1; for(int i=1;i<=len;i++) { if(s[i]==s[i+1]) //偶數長度的回文數組條件 { a=get(min(2*i,len),i,i+1); ans=max(2*a,ans); } if(s[i-1]==s[i+1]) //偶數長度的回文數組條件 { b=get(min(2*i-1,len),i-1,i+1); ans=max(2*b+1,ans); } } printf("%d ",ans); } }
切記scanf讀入字符串時，EOF不能終止while語句，要加上“~”