2021-04-08 PAT A1040 hash + 二分

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MAXN = 1010,MOD = 1000000007,P = 10000017;//P是进制，MOD是模数
LL powP[MAXN],H1[MAXN],H2[MAXN];
void init(){
    powP[0] = 1;
    for(int i = 1;i < MAXN;i++) powP[i] = ( powP[i - 1] * P ) % MOD;
}
void calH(LL H[],char* str){//计算对应字符串的HASH值
    H[0] = str[0];
    int len = strlen(str);
    for(int i = 1;i < len;i++) H[i] = (P * H[i - 1] + str[i]) % MOD;
}
LL calSingleSubH(LL H[],int i,int j){//计算从I到J的子串
    if(i == 0) return H[j];
    return ((H[j] - H[i - 1] * powP[j - i + 1]) % MOD + MOD) %MOD;
}
//如果是偶数的话，那么even就等于1，因为偶数的话，计算半径的时候有影响
int binarySearch(int l, int r, int len,int i,int isEven){//i是中心点，然后在l和r中间二分半径
    while(l < r){
        int mid = (r + l) / 2;//这个是半径
        if(calSingleSubH(H1,i - mid + isEven,i) != calSingleSubH(H2,(len - 1 - i - mid),(len - 1 - (i + isEven)))) r = mid;//如果不相等，那么就缩小半径
        else l = mid + 1;//如果相等，那么就加大半径
    }
    return l - 1;//这里的l是第一个让子串不相等的半径大小
}
int main(){
    init();
    char str[MAXN];scanf("%[^\n]s",str);
    calH(H1,str);
    int len = strlen(str);
    reverse(str,str + len);
    calH(H2,str);
    int ans = 0;//记录最长子串
    for(int i = 0;i < len;i++){//i是奇数
        int maxlen = min(i,len - 1 - i) + 1;//这个是二分上界，也就是i的左右的长度，因为是奇数，左右长度不受影响
        int temp = binarySearch(0,maxlen,len,i,0) * 2 + 1;
        if(temp > ans) ans = temp;
    }
    for(int i = 0;i < len;i++){//i是偶数
        int maxlen = min(i + 1,len - 1 - i) + 1;
        binarySearch(0,maxlen,len,i,0);//左右长度受影响，因为是偶数，左长度要加一
        int temp = binarySearch(0,maxlen,len,i,1) * 2 ;
        if(temp > ans) ans = temp;
    }
    
    printf("%d",ans);
}