rt

本人用的 SA 正确性应该没啥问题。

MLE 的测试点本地跑出来都是正常的。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define N 10000005

using namespace std;
int n,k,len;
char s[N];

int rk[N],h[N];

namespace SAIS {
    int sa[N];

    bool isLMS(int x,bool *tpy) { return x>0 and tpy[x] and !tpy[x-1]; }

    template<typename T>
    bool sameLMS(int x,int y,T s,int len,bool *tpy) {
        if (x<=0 or y<=0 or s[x]!=s[y] or tpy[x]!=tpy[y]) return 0;
        for (int i=1;;i++) {
            if (tpy[x+i]!=tpy[y+i] or s[x+i]!=s[y+i]
                or isLMS(x+i,tpy)!=isLMS(y+i,tpy)) return 0;
            if (isLMS(x+i,tpy)) return 1;
        }
        return 0;
    }

    template<typename T>
    void inducesort(T s,int len,int *LMS,int LMScnt,bool *tpy,int sigma) {
        int *t=new int[sigma],*sum=new int[sigma];
        memset(sa,-1,len*sizeof(sa[0]));
        memset(t,0,sigma*sizeof(t[0]));
        for (int i=0;i<len;i++) t[s[i]]++;
        sum[0]=t[0];
        for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+t[i];
        for (int i=LMScnt-1;i>=0;i--) sa[--sum[s[LMS[i]]]]=LMS[i];
        sum[0]=0;
        for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+t[i-1];
        for (int i=0;i<len;i++) {
            if (sa[i]<=0 or tpy[sa[i]-1]) continue;
            sa[sum[s[sa[i]-1]]++]=sa[i]-1;
        }
        sum[0]=t[0];
        for (int i=1;i<sigma;i++) sum[i]=sum[i-1]+t[i];
        for (int i=len-1;i>=0;i--) {
            if (sa[i]<=0 or !tpy[sa[i]-1]) continue;
            sa[--sum[s[sa[i]-1]]]=sa[i]-1;
        }
        delete[] sum,t;
    }

    template<typename T>
    void sais(T s,int len,int *LMS,int sigma) {
        bool *tpy=new bool[len];
        tpy[len-1]=1;
        for (int i=len-2;i>=0;i--)
            if (s[i]>s[i+1]) tpy[i]=0;
            else if (s[i]<s[i+1]) tpy[i]=1;
            else tpy[i]=tpy[i+1];
        int LMScnt=0;
        for (int i=0;i<len;i++)
            if (isLMS(i,tpy)) LMS[LMScnt++]=i;
        inducesort(s,len,LMS,LMScnt,tpy,sigma);
        int pre=-1,cnt=0; int *tmp=new int[len];// sa
        for (int i=0;i<len;i++) {
            if (!isLMS(sa[i],tpy)) continue;
            if (!sameLMS(sa[i],pre,s,len,tpy)) ++cnt;
            tmp[sa[i]]=cnt-1,pre=sa[i];
        }
        int *s1=new int[LMScnt],*tLMS=new int[LMScnt];// rk
        for (int i=0;i<LMScnt;i++) s1[i]=tmp[LMS[i]];
        if (LMScnt!=cnt) sais(s1,LMScnt,tLMS,cnt);
        else for (int i=0;i<LMScnt;i++) sa[s1[i]]=i;
        for (int i=0;i<LMScnt;i++) tLMS[i]=LMS[sa[i]];
        inducesort(s,len,tLMS,LMScnt,tpy,sigma);
        delete[] tpy,tmp,s1,tLMS;
    }

    template<typename T>
    void init(T s,int len,int *rk,int *h) {
        int *LMS=new int[len+1];
        sais(s,len+1,LMS,27);
        for (int i=0;i<len;i++) sa[i]=sa[i+1];
        for (int i=0;i<len;i++) rk[sa[i]]=i;
        for (int i=0,k=0;i<len;i++) {
            if (!rk[i]) continue;
            if (k) k--;
            while (s[i+k]==s[sa[rk[i]-1]+k]) k++;
            h[rk[i]]=k;
        }
        delete[] LMS;
    }
} using SAIS::sa;

int main() {
    // freopen("1.in","r",stdin);
    scanf("%d",&n);
    for (int i=0;i<n;i++) {
        cin>>s[i]; s[i]=s[i]-'a'+1;
        s[i+n]=s[i];
    }
    n<<=1;
    SAIS::init(s,n,rk,h);
    int pos=-1;
    for (int i=0;i<n;i++)
        if (sa[i]<(n>>1) and h[i+1]<n-sa[i]) { pos=sa[i]; break; }
    printf("%d\n",pos);
    return 0;
}