Настер і паліндромічні зрушення#12350

Настер і паліндромічні зрушення (Розбір)

Автор задачі:	Mohammad Nasser (MOAGEZA)
Підготовка:	Mohammad Nasser (MOAGEZA)
Редактура:	Hasan Saleh (MathModel)

Розв'язок

Загальна ідея

Зверніть увагу, що виконання зсувів вліво або вправо еквівалентно повороту рядка. Отже, задача зводиться до перевірки, чи є якийсь поворот рядка паліндромом, та пошуку мінімального числа поворотів, необхідного для цього.

Перевірка кожного повороту наївним способом займе $O (n^{2})$ \mathcal{O}(n^2), що є надто повільним. Замість цього ми використовуємо подвійне рулонне хешування, щоб порівнювати підрядки за сталий час після лінійної передобробки.

Підготовка хешу

Ми обчислюємо префіксні хеші для рядка, а також для його перевернутої версії.

Використання поліноміального хешування з двома модулями знижує ймовірність колізій і дозволяє безпечно порівнювати підрядки.

Хеш підрядка можна отримати за $O (1)$ за допомогою:

H (l, r) = p r e [r] - p r e [l - 1] \cdot ba s e^{(r - l + 1)}

H(l,r) = pre[r] - pre[l-1] \cdot base^{(r-l+1)}

Перевірка на паліндром

Підрядок є паліндромом, якщо він дорівнює своєму перевернутому варіанту.

Використовуючи хеші:

s [l .. r] є паліндромом ⟺ H_{f or w a r d} (l, r) = H_{r e v er se} (n - r - 1, n - l - 1)

s[l..r] \text{ є паліндромом } \iff H_{forward}(l,r) = H_{reverse}(n-r-1, n-l-1)

Пошук мінімального зсуву

По-перше, перевіряємо, чи є початковий рядок уже паліндромом. Якщо так, відповідь - $0$ .

Інакше пробуємо повороти.

Повороти вліво

Після зсуву вліво на $i$ , рядок стає:

s [i .. n - 1] + s [0.. i - 1]

s[i..n-1] + s[0..i-1]

Перевіряємо:

1. Основний середній сегмент є паліндромом. 2. Префікс відповідає перевернутої суфіксу.

Як тільки знайдено перший допустимий поворот, записуємо $i$ .

Повороти вправо

Поворот вправо еквівалентний зміні перспективи рядка на протилежну та застосуванню тієї ж логіки.

Ми відповідно перевирахуємо хеші та шукаємо знову.

Мінімальний допустимий зсув між лівими та правими поворотами є відповіддю.

Якщо жоден поворот не утворює паліндром, виведіть $- 1$ .

Аналіз складності

Передобчислення степенів: $O (n)$
Побудова префіксних хешів: $O (n)$
Перевірка поворотів: $O (n)$

Таким чином, загальна складність на один тестовий випадок є:

O (n)

зі сталими перевірками на паліндром.

//author : MOAGEZA
#include <bits/stdc++.h>
#define ll long long
#define Moageza ios::sync_with_stdio(false);cin.tie(NULL);
using namespace std;

const int N=1e6+5,base1=127,base2=131;
const int mod1=1e9+7,mod2=2e9+11;

int n,pw1[N],pw2[N];
pair<int,int>pre[N],suf[N];

void init(){
    pw1[0]=pw2[0]=1;
    for(int i=1;i<N;i++){
        pw1[i]=(1LL*pw1[i-1]*base1)%mod1;
        pw2[i]=(1LL*pw2[i-1]*base2)%mod2;
    }
}

void Hash(string&s,pair<int,int>arr[]){
    int a=0,b=0;
    for(int i=0;i<s.size();i++){
        a=(1LL*a*base1+s[i])%mod1;
        b=(1LL*b*base2+s[i])%mod2;
        arr[i]={a,b};
    }
}

pair<int,int>get(int l,int r,pair<int,int>arr[]){
    auto ret=arr[r];
    int sz=r-l+1;
    if(l>0){
        ret.first=(ret.first-1LL*arr[l-1].first*pw1[sz]%mod1+mod1)%mod1;
        ret.second=(ret.second-1LL*arr[l-1].second*pw2[sz]%mod2+mod2)%mod2;
    }
    return ret;
}

bool pal(int l,int r){
    return get(l,r,pre)==get(n-r-1,n-l-1,suf);
}

void solve(){
    cin>>n;
    string s;cin>>s;

    Hash(s,pre);
    reverse(s.begin(),s.end());
    Hash(s,suf);
    reverse(s.begin(),s.end());

    if(pal(0,n-1)){
        cout<<0;
        return;
    }

    int ans=-1;

    // left shifts
    for(int i=1;i<(n+1)/2;i++){
        if(pal(2*i,n-1)&&get(n-i,n-1,suf)==get(i,2*i-1,pre)){
            ans=i;
            break;
        }
    }

    // right shifts
    reverse(s.begin(),s.end());
    Hash(s,pre);
    reverse(s.begin(),s.end());
    Hash(s,suf);

    for(int i=1;i<(n+1)/2;i++){
        if(pal(2*i,n-1)&&get(n-i,n-1,suf)==get(i,2*i-1,pre)){
            if(ans==-1||i<ans) ans=i;
            break;
        }
    }

    cout<<ans;
}

int main(){
    Moageza
    init();

    int t;cin>>t;
    while(t--){
        solve();
        cout<<"\n";
    }
}