（加强版）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<bits/stdc++.h>
#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<int,int> 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<<'
';}template<typename T,typename... Args>void debug(T x,Args... args){cerr<<"[ "<<x<< " ] , ";debug(args...);}
mt19937 mt19937random(std::chrono::system_clock::now().time_since_epoch().count());
ll getRandom(ll l,ll r){return uniform_int_distribution<ll>(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<M;i++)cnt[i]=0;
for(i=0;i<n;i++)cnt[x[i]=str[i]]++;
for(i=1;i<M;i++)cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;i--)sa[--cnt[x[i]]]=i;
for(j=1,p=1;p<n;j<<=1,M=p){
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
for(i=0;i<M;i++)cnt[i]=0;
for(i=0;i<n;i++)cnt[x[y[i]]]++;
for(i=1;i<M;i++)cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;i--)sa[--cnt[x[y[i]]]]=y[i];
for(swap(x,y),p=1,x[sa[0]]=0,i=1;i<n;i++)
x[sa[i]]=(y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+j]==y[sa[i]+j])?p-1:p++;
}
}
void getHeight(int n){
int i,j,k=0;
for(i=1;i<=n;i++)rk[sa[i]]=i;
for(i=0;i<n;height[rk[i++]]=k)
for(k?k--:0,j=sa[rk[i]-1];str[i+k]==str[j+k];k++);
for(i=n;i;i--)rk[i]=rk[i-1],sa[i]++;
}
void solve()
{
int n;
string s,t;
cin>>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<n) //已经变了的话则直接结束寻找即可
break;
}
}
}
cout<<ans<<'
';
}
int main()
{
closeSync;
//multiCase
{
solve();
}
return 0;
}