C++14(g++5.4) 解法, 执行用时: 89ms, 内存消耗: 6948K, 提交时间: 2019-12-08 19:34:48

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9+7;
int main() {
  int n; cin >> n;
  string A; cin >> A;
  vector<int> H(n+1); for (int i = 0; i < n; i++) H[i + 1] = H[i] * P + A[i];
  vector<int> I(n+1); for (int i = n - 1; i >= 0; i--) I[i] = I[i + 1] * P + ('1' + '0' -A[i]);
  vector<int> B(n+1, 1); for (int i = 0; i < n; i++) B[i + 1] = B[i] * P;

  long long tot = 0;
  for (int i = 0; i < n; i++) {
    int lo = 0, hi = min(i + 1, n - i - 1)+1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      // cout << i << " " << lo << " " << hi << " " << mid << endl;
      if (H[i+1] - H[i+1- mid] * B[mid] == I[i+1] - I[i+1+mid]*B[mid]) lo = mid + 1;
      else hi = mid;
    }
    tot += hi - 1;
  }
  cout << tot << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 15ms, 内存消耗: 5984K, 提交时间: 2020-06-27 19:22:11

#include<bits/stdc++.h>
#define ull unsigned long long
using namespace std;
int n;
ull ans;
int r[1000001];
char s[500001],c[1000001];
int main() {
    scanf("%d%s",&n,s+1);
    c[0]='$';
    for(int i=1;i<=n;i++) {
        c[2*i-1]='#';
        c[2*i]=s[i];
    }
    c[2*n+1]='#'; c[2*n+2]='$';
    int mx=0,po=0;
    for(int i=1;i<=2*n;i+=2) {
        if(mx>i) r[i]=min(mx-i,r[2*po-i]);
        else r[i]=1;
        while((c[i+r[i]]==c[i-r[i]]&&c[i+r[i]]=='#')||(c[i+r[i]]-'0'+c[i-r[i]]-'0'==1))
            r[i]++;
        if(i+r[i]>mx) mx=i+r[i],po=i;
        ans+=r[i]>>1;
    }
    printf("%lld\n",ans);
    return 0;
}