首页 > Web开发 > 详细

[JSOI2016]扭动的回文串

时间:2019-04-01 22:27:03      阅读:209      评论:0      收藏:0      [点我收藏+]

技术分享图片


题解

可以发现最后的答案一定长成\(A\)串和\(B\)串的一对对称的子串(长度可以为\(0\))
然后中间夹着\(A\)串或者\(B\)串中的一个回文串(长度可以为\(0\))
对于每一个中心点,对应的最大的答案中间所夹的那个回文串一定是以这个中心点为对称中心的最长回文串
那么就从以这个中心点为对称中心的最长回文串的两边开始找那个\(A\)串和\(B\)串的对称部分
看看两边最长能扩展多长,二分+哈希判断即可

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define ull unsigned long long
const int M = 200010 ;
const ull Base = 233 ;
using namespace std ;

char s1[M] , s2[M] , p[M] ;
ull pw[M] , hsh1[M] , hsh2[M] ;
int n , m , ans , r[M] , posi[M] ;
inline bool Same(int l1 , int r1 , int l2 , int r2) {
    if(l1 > r1) swap(l1 , r1) ; if(l2 > r2) swap(l2 , r2) ;
    ull tp1 = hsh1[l1] - hsh1[r1 + 1] * pw[r1 - l1 + 1] ;
    ull tp2 = hsh2[r2] - hsh2[l2 - 1] * pw[r2 - l2 + 1] ;
    return (tp1 == tp2) ;
}
inline void update(int lpos , int rpos , int dlt) {
    if(dlt < 0) {
        int l = 1 , r = min(lpos - 1 , n - rpos + 1) , ret = 0 , mid ;
        while(l <= r) {
            mid = (l + r) >> 1 ;
            if(Same(lpos - mid , lpos - 1 , rpos , rpos + mid - 1)) ret = mid , l = mid + 1 ;
            else r = mid - 1 ;
        }
        ans = max(ans , rpos - lpos + 1 + ret * 2) ;
    }
    else {
        int l = 1 , r = min(lpos , n - rpos) , ret = 0 , mid ;
        while(l <= r) {
            mid = (l + r) >> 1 ;
            if(Same(lpos - mid + 1 , lpos , rpos + 1 , rpos + mid)) ret = mid , l = mid + 1 ;
            else r = mid - 1 ;
        }
        ans = max(ans , rpos - lpos + 1 + ret * 2) ;
    }
}
inline void Manacher(char *s , int dlt) {
    m = 0 ; p[++m] = '$' ;
    for(int i = 1 ; i <= n ; i ++) {
        p[++m] = '#' ; posi[m] = i ;
        p[++m] = s[i] ; posi[m] = i ;
    }
    p[++m] = '#' ; posi[m] = n + 1 ; p[++m] = '@' ; 
    int mx = 0 , pos = 0 ;
    for(int i = 1 ; i <= m ; i ++) {
        if(mx > i) r[i] = min(mx - i , r[pos * 2 - i]) ; else r[i] = 1 ;
        while(p[i - r[i]] == p[i + r[i]]) ++ r[i] ;
        if(i + r[i] > mx) mx = i + r[i] , pos = i ;
        update(posi[i - r[i] + 1] , posi[i + r[i] - 1] - 1 , dlt) ;
    }
}
int main() {
    scanf("%d",&n) ; scanf("%s",s1 + 1) ;  scanf("%s",s2 + 1) ; 
    pw[0] = 1 ; for(int i = 1 ; i <= n ; i ++) pw[i] = pw[i - 1] * Base ;
    for(int i = n ; i >= 1 ; i --) hsh1[i] = hsh1[i + 1] * Base + s1[i] ;
    for(int i = 1 ; i <= n ; i ++) hsh2[i] = hsh2[i - 1] * Base + s2[i] ;
    Manacher(s1 , -1) ; Manacher(s2 , 1) ;
    printf("%d\n",ans) ;
    return 0 ;
}

[JSOI2016]扭动的回文串

原文:https://www.cnblogs.com/beretty/p/10639068.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!