A M形字符

题意：

M形字符串指的是由两个相同的回文串拼接而成

给你一个串S，问有多少个前缀是M形字符串

思路：

M形是有两个相同的回文串构成的，所以这个M形串本身就是回文串，我们只需要判断一个串是回文串的同时，他的一半也是回文串即可

那如何判是不是回文串呢，这里我们使用哈希进行判断

如果一个串的正序哈希值等于其逆序哈希，则说明这个串是回文串

哈希的计算方法：

pre[i] = pre[i - 1] * seed + s[i] - 'a' + 1;

对于中间取的一段的哈希值，我们可以利用类似于差分的方法

pre[r] - pre[l - 1] * base[r - l + 1];

乘base[r - l + 1]是为了将其化为“同阶”

AC码：

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1500000 + 7
#define endl '\n'
#define seed 1331
const int mod = 1e9 + 7;
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
//#define mod 571373;
typedef  long long ll ;
//不开longlong见祖宗！

inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int pre[MAX], back[MAX], base[MAX];
string s;
ll   len;

int idx(char x){
    return (int)(x - 'a' + 1);
}

int getpre(int l, int r){//获得区间[l, r]的顺序哈希值
    return pre[r] - pre[l - 1] * base[r - l + 1];
}

int getback(int l, int r){//获得区间[l, r]的逆序哈希值
    return back[r] - back[l - 1] * base[r - l + 1];
}

bool judge(int i, int j){//判断正逆序的哈希是否相同
    return getpre(i, j) == getback(len - j + 1, len - i + 1);
}

int half(int x){
    return (x + 1) / 2;
}

int main(){
    cin>>s;
    s = " " + s;
    len = s.size();
    base[0] = 1;
    for(int i = 1; i <= len; ++i){
        base[i] = base[i - 1] * seed;
        pre[i] = (pre[i - 1] * seed + idx(s[i]));
        back[i] = (back[i - 1] * seed + idx(s[len - i + 1]));
    }
    int ans = 0;
    for(int i = 1; i <= len; ++i){
      //如果这个串是回文串，且他的一半也是回文串，就更新答案
        if(judge(1, i) && judge(1, half(i)))ans++;
    }
    cout<<ans<<endl;
    return 0;
}