ZJNU 1397 - 隐藏口令 （后缀数组）

ZJNU 1397 - 隐藏口令

（加强版）Luogu 1709 - [USACO5.5]隐藏口令Hidden Password

题面

思路

大家都是最小表示法？我不会，我只会后缀数组了哭哭

后缀数组\(sa[i]\)可以表示排名为\(i\)?的后缀起始位置下标

又因为题目要求字符串可循环，为了能够让后缀数组进行处理，将原串扩展一倍后跑后缀数组

其后对于这个长度为\(2n\)?的串，从最高排名开始寻找\(sa[i]\le n\)的位置，这说明这一段表示的后缀在原串中是最小的

如果可以任意输出编号，那么找到的第一个位置的\(sa[i]\)就可以直接输出了，但本题要求字符串相同时需要输出编号最小的

考虑后缀数组的\(height[i]\)?表示排名为\(i\)和\(i-1\)的两个后缀的最长公共前缀长度

假如我们找到了第一个满足\(sa[i]\le n\)的位置\(i\)，先记录下位置\(i\)，然后初始化变量\(pre=n\)，表示从\(i\)位置开始向后处理的过程中，连续排名的这些后缀的最长公共前缀长度，所以从\(i\)位置向后寻找时，每次都需要让\(pre=\min(pre,height[i])\)更新最长公共前缀长度

假如我们在\(i\)位置后面又找到了一个新的位置\(j\)满足\(sa[j]\le n\)，并且此时\(pre=n\)仍然成立，则说明\(i\)位置开始的口令与\(j\)位置开始的口令是相同的，所以更新答案为\(\min(sa[i],sa[j])\)，即最小编号；反之，如果\(pre=n\)?已经不成立了，那么就不需要再更新答案，此前找到的\(i\)已是最优解

#include
#define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define multiCase int T;cin>>T;for(int t=1;t<=T;t++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i<(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define perr(i,a,b) for(int i=(a);i>(b);i--)
#define all(a) (a).begin(),(a).end()
#define mst(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair P;
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const double eps=1e-12;
const double PI=acos(-1.0);
const ll mod=998244353;
const int dx[8]={0,1,0,-1,1,1,-1,-1},dy[8]={1,0,-1,0,1,-1,1,-1};
void debug(){cerr<<'\n';}templatevoid debug(T x,Args... args){cerr<<"[ "<(l,r)(mt19937random);}
ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}
ll qmul(ll a,ll b){ll r=0;while(b){if(b&1)r=(r+a)%mod;b>>=1;a=(a+a)%mod;}return r;}
ll qpow(ll a,ll n){ll r=1;while(n){if(n&1)r=(r*a)%mod;n>>=1;a=(a*a)%mod;}return r;}
ll qpow(ll a,ll n,ll p){ll r=1;while(n){if(n&1)r=(r*a)%p;n>>=1;a=(a*a)%p;}return r;}

const int N=200050;
int xx[N],yy[N],cnt[N];
int sa[N],rk[N],height[N];
char str[N];
void getSA_DA(int n,int M){
    int i,j,p,*x=xx,*y=yy;
    for(i=0;i=0;i--)sa[--cnt[x[i]]]=i;
    for(j=1,p=1;p=j)y[p++]=sa[i]-j;
        for(i=0;i=0;i--)sa[--cnt[x[y[i]]]]=y[i];
        for(swap(x,y),p=1,x[sa[0]]=0,i=1;i>n;
    while(cin>>t)
        s+=t;
    s+=s;
    repp(i,0,n+n)
        str[i]=s[i];
    
    getSA_DA(n+n+1,128);
    getHeight(n+n);
    
    int ans=-1,pre=-1;
    
    rep(i,1,n+n) //此时长度为2n
    {
        pre=min(pre,height[i]); //更新pre
        if(sa[i]<=n) //假如找到合法串
        {
            if(ans==-1) //此前没找到过答案，则该位置是暂时的最优解
            {
                ans=sa[i]-1;
                pre=n; //定此时最长公共前缀为n
            }
            else
            {
                if(pre==n) //最长公共前缀不变，编号取小
                    ans=min(ans,sa[i]-1);
                else if(pre