Antisymmetry

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1302 字

哈希二分反对称半径统计合法子串

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1462
// 题意：给长度 N 的 01 串，统计有多少个子串是"反对称"的（取反再反转后与原串相同）。
// 思路：预处理原串与"取反并反转"串的滚动哈希，枚举偶数长度中心 i，二分最大半径 L 使左右两半互为反串，答案累加 L。
// 复杂度：O(N·log N) 时间 / O(N) 空间
// 易错点：反对称子串长度必为偶数，只枚举中心在两字符之间的情况；答案可达 N^2 量级，必须用 long long。
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BS=911382323ull;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin>>n)) return 0;
    string s;
    if(!(cin>>s)) return 0;
    string t(n,'0');
    for(int i=0;i<n;i++){
        t[i]=(s[n-1-i]=='0'?'1':'0');
    }
    vector<ull> hs(n+1,0),ht(n+1,0),pw(n+1,1);
    for(int i=0;i<n;i++){
        hs[i+1]=hs[i]*BS+(ull)(unsigned char)s[i];
        ht[i+1]=ht[i]*BS+(ull)(unsigned char)t[i];
        pw[i+1]=pw[i]*BS;
    }
    auto gs=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return hs[r+1]-hs[l]*pw[r-l+1];
    };
    auto gt=[&](int l,int r)->ull{
        if(l>r) return 0ull;
        return ht[r+1]-ht[l]*pw[r-l+1];
    };
    long long ans=0;
    for(int i=1;i<n;i++){
        int lo=0,hi=min(i,n-i);
        while(lo<hi){
            int mid=(lo+hi+1)/2;
            if(gs(i-mid,i-1)==gt(n-i-mid,n-1-i)) lo=mid;
            else hi=mid-1;
        }
        ans+=lo;
    }
    cout<<ans<<'\n';
    return 0;
}

Antisymmetry

正文

一本通·提高篇的其它内容