回文字D

题目：https://ac.nowcoder.com/acm/contest/11169

• 从左到右，从右到左分别求一次字符串hash值
• 从字符串起点每次枚举长度为D的字符串，如果是回文串，继续往后枚举，如果不是回文串ans++

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL; 
const int INF=0x3f3f3f3f;
const int N=1e7+5, P=131;
ULL h[N], rh[N], p[N];
char s[N];

bool check(int l, int r){
    return h[r]-h[l-1]*p[r-l+1]==rh[l]-rh[r+1]*p[r-l+1];
} 

int main(){
    int n,d;
    cin>>n>>d;
    cin>>s+1;
    p[0]=1;
    for(int i=1; i<=n; i++){
        h[i]=h[i-1]*P+s[i];
        p[i]=p[i-1]*P;
    }

    for(int i=n; i>=1; i--){
        rh[i]=rh[i+1]*P+s[i];
    }

    int ans=0;

    for(int i=1, j; i<=n; i=j+1){
        j=i+d-2;
        while(j+1<=n&&check(j+1-d+1, j+1)) j++;  //j+1<=n,处理了边界问题
        ans++;
    }
    cout<<ans<<endl;
    return 0;
}