|
#include <bits/stdc++.h> using namespace std; int base=4;//进位 int mod=1000000007;//最大的数字 int getcharhs(char c){ return c-'a'+1; } //获取一个字符串的所有前缀哈希值 vector<long long> getqz(string s){ vector<long long> hs(s.size()+1,0); for(int i=1;i<=s.size();i++){ hs[i]=(hs[i-1]*base+getcharhs(s[i-1]))%mod; } return hs; } //获取一个字符串的所有后缀哈希值 vector<long long> gethz(string s){ vector<long long> hs(s.size()+1,0); long long basepow=base; hs[s.size()-1]=getcharhs(s[s.size()-1]); for(int i=s.size()-2;i>=0;i--){ hs[i]=(getcharhs(s[i])*basepow+hs[i+1])%mod; basepow*=base; basepow%=mod; } return hs; } //获取任意一段子串的哈希值 long long getstrhs(vector<long long> hs,int l,int r){ long long basepow=round(pow(base,(r-l+1))); basepow%=mod; return hs[r]-hs[l-1]*basepow; } int main(){ string s ="11001010"; string fs=""; for(int i=0;i<s.size();i++) fs[i]=(s[i]=='1'?'0':'1'); vector<long long> a=getqz(s),b=getqz(fs); long long ans=0; for(int i=1;i<s.size();i++){//确定实际查找范围：左<-i->右 下标0～s.size()-1,中轴i,左:0~i-1,右:i~s.size()-1 int leftl=i-1,rightl=s.size()-1-i+1; int l,r=i; if(leftl>=rightl) l=leftl-rightl; else l=0; while(l<r){ int mid=(l+r)/2; int li=i-1-mid; if(getstrhs(a,mid,i-1)==getstrhs(b,i,i+li)) r=mid; else l=mid+1; }//反对称子串数量=k~i字符数量 ans+=i-l;//累加 } return 0; } |