Nasser və Palindromik Keçidlər#12350

Nasser və Palindromik Keçidlər (Həll təhlili)

Problemin Müəllifi:	Mohammad Nasser (MOAGEZA)
Hazırlayan:	Mohammad Nasser (MOAGEZA)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Ümumi Fikir

Soldan və ya sağdan yerini dəyişmək sətirin dövr etməsi ilə bərabərdir. Buna görə, problem sətirin hansısa bir dövrünün palindrom olub-olmadığını yoxlamağa və minimal dövr sayını tapmağa enmiş olur.

Hər dövrü sadəcə yoxlamaq $O (n^{2})$ \mathcal{O}(n^2) vaxt alar ki, bu da çox yavaşdır. Əvəzində, substratları dairəvi müqayisə üçün xətti əvvəlki işləmə sonrası ikiqat dövri həşlə istifadə edirik.

Həş Hazırlığı

Sətir üçün prefiks həşləri və onun tərsinə çevrilmiş versiyası üçün hesablayırıq.

İki modul ilə polinomial həşləndirmə toqquşma ehtimalını azaldır və etibarlı substratların müqayisəsini mümkün edir.

Alt yerdəyişmənin həşi $O (1)$ əldə edilə bilər, istifadə edərək:

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)}

Palindrom Yoxlaması

Alt yerdəyişmə palindromdur, əgər onun tərsinə çevrilmiş əksinə bərabərdirsə.

Həşlərdən istifadə edərək:

s [l .. r] palindromdur ⟺ 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{ palindromdur } \iff H_{forward}(l,r) = H_{reverse}(n-r-1, n-l-1)

Minimal Yerdəyişmələrin Tapılması

Əvvəlcə, əgər orijinal sətir artıq palindromdursa yoxlayırıq. Əgər bəli, cavab $0$ -dır.

Əks halda, dövrləri yoxlayırıq.

Sol dövrlər

Soldan $i$ qədər dövr etdikdən sonra, sətir belə olur:

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

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

Biz təsdiq edirik:

1. Əsas orta seqment palindromdur. 2. Prefiks tərsinə çevrilmiş sonluğu ilə uyğun gəlir.

İlk uyğun dövr tapıldıqda, $i$ qeyd edilir.

Sağ dövrlər

Sağ dövr perspektivini tersin çevirməklə bərabərdir və eyni məntiq tətbiq edilir.

Həşləri yenidən hesablayırıq və yenidən axtarırıq.

Sol və sağ dövrlər arasında minimal uyğun yerdəyişmə cavabdır.

Əgər heç bir dövr palindrom təşkil etmirsə, $- 1$ çap edilir.

Çətinlik Təhlili

Güclərin əvvəlcədən hesablanması: $O (n)$
Prefiks həşlərinin hazırlanması: $O (n)$
Dövrlərin yoxlanması: $O (n)$

Buna görə, hər test vəziyyəti üçün ümumi çətinlik:

O (n)

sabit vaxtda palindrom yoxlamalar ilə.

//müəllif : 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;

    // sol dövrlər
    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;
        }
    }

    // sağ dövrlər
    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";
    }
}