题目概述

String Problem

解题报告

首先很显然，对于前缀 $i$ ，答案一定是某一个位置到 $i$ 。

用后缀数组可以做，但是思考起来比较麻烦。

考虑后缀自动机，在建立后缀自动机的时候我们记录一下 $pos_x$ 表示 $x$ 节点的对应前缀，由于在后缀自动机上优先跑最大边就可以获得最大子串，因此如果我们按照最大边跑到了 $x$ 点，经过了 $len$ 个字符，如果 $pos_x$ 之前没有被访问过，那么前缀 $pos_x$ 的对应起始位置就是 $pos_x-len+1$ 。

但是遍历后缀自动机的复杂度是 $O(n^2)$ 的，我们能不能不重复经过相同的点？答案是肯定的，因为重复经过相同点的时候肯定没有之前的字符串字典序大，因此没必要重复经过相同的点。

还有一个问题是，我们知道一个节点 $x$ 其实包含了所有parent树子树的前缀，为什么只需要更新前缀 $pos_x$（也就是最小的前缀）？其实也很显然，经历了相同的字符到达一个后缀，那么靠前的前缀 $pos_x$ 往后接字符一定比后面不接字符的前缀大，即后面前缀的答案不可能是 $x$ 节点带来的。

示例程序

#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=2000000;

int n,ans[maxn+5];char s[maxn+5];
int pl,ro,son[maxn+5][26],fai[maxn+5],MAX[maxn+5],pos[maxn+5];
bool vis[maxn+5];

inline int newnode(int m) {pl++;MAX[pl]=m;return pl;}
int Extend(int p,int c,int ID){
    int np=newnode(MAX[p]+1);pos[np]=ID;
    while (p && !son[p][c]) son[p][c]=np,p=fai[p];
    if (!p) {fai[np]=ro;return np;}
    int q=son[p][c];
    if (MAX[p]+1==MAX[q]) {fai[np]=q;return np;}
    int nq=newnode(MAX[p]+1);pos[nq]=pos[q];
    for (int i=0;i<26;i++) son[nq][i]=son[q][i];
    fai[nq]=fai[q];fai[np]=fai[q]=nq;
    while (p && son[p][c]==q) son[p][c]=nq,p=fai[p];
    return np;
}
void DFS(int x,int len=0){
    vis[x]=true;
    for (int i=25,u;~i;i--)
        if ((u=son[x][i]) && !vis[u]) DFS(u,len+1);
    if (pos[x] && !ans[pos[x]]) ans[pos[x]]=len;
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    ro=newnode(0);
    for (int i=1,p=ro;i<=n;i++) p=Extend(p,s[i]-'a',i);
    DFS(ro);
    for (int i=1;i<=n;i++) printf("%d %d\n",i-ans[i]+1,i);
    return 0;
}

这里也附上后缀数组的做法（简单注释）。

#include<cstdio>
#include<cctype>
#include<algorithm>
#define fr first
#define sc second
#define mp make_pair
using namespace std;
const int maxn=1000000,LOG=20;

int n;char s[maxn+5];
int SA[maxn+5],rk[maxn+5],ha[maxn+5],t[(maxn<<1)+5];
int lg[maxn+5],RMQ[maxn+5][LOG+1];

inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
void Sort(int n,int m){
    for (int i=0;i<=m;i++) ha[i]=0;for (int i=1;i<=n;i++) ha[rk[i]]++;
    for (int i=1;i<=m;i++) ha[i]+=ha[i-1];for (int i=n;i;i--) SA[ha[rk[t[i]]]--]=t[i];
}
void Make(int n,int m=255){
    for (int i=1;i<=n;i++) rk[i]=s[i],t[i]=i,t[i+n]=0;Sort(n,m);
    for (int k=1,p=0;p<n;m=p,k<<=1){
        p=0;for (int i=n-k+1;i<=n;i++) t[++p]=i;
        for (int i=1;i<=n;i++) if (SA[i]>k) t[++p]=SA[i]-k;
        Sort(n,m);for (int i=1;i<=n;i++) t[i]=rk[i];rk[SA[1]]=p=1;
        for (int i=2;i<=n;i++) rk[SA[i]]=(p+=t[SA[i-1]]!=t[SA[i]] || t[SA[i-1]+k]!=t[SA[i]+k]);
    }
    for (int i=1,k=0;i<=n;i++){
        if (k) k--;while (s[i+k]==s[SA[rk[i]-1]+k]) k++;
        RMQ[rk[i]][0]=k;
    }
    RMQ[1][0]=0;
    for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1;
    for (int j=1;(1<<j)<=n;j++)
        for (int i=1;i+(1<<j)-1<=n;i++)
            RMQ[i][j]=min(RMQ[i][j-1],RMQ[i+(1<<j-1)][j-1]);
}
int LCP(int L,int R){
    L++;int k=lg[R-L+1];
    return min(RMQ[L][k],RMQ[R-(1<<k)+1][k]);
}
int main(){
    for (char ch=readc();islower(ch);ch=readc()) s[++n]=ch;
    Make(n);//for (int i=1;i<=n;i++) puts(s+SA[i]);
    int lst=1,MIN=1e9,who=0,nxtMIN=1e9,nxtwho=0;
    //lst表示当前最优解，不难发现lst肯定是不降的
    //MIN表示当前最靠前的更新点（即当i到达MIN时，lst将更新为who）
    //who表示更新点对应的后缀
    //nxtMIN和nxtwho同理，但是是针对who的更新
    //lst更新为who之后，会有一段没有用来更新lst（因为之前都在针对lst更新）
    //为了避免这种情况，需要同时记录针对who的更新
    for (int i=1;i<=n;i++){
        if (rk[i]>rk[lst]){ //如果i后缀比lst后缀排名高，肯定会在某个位置i比lst大
            int now=i+LCP(rk[lst],rk[i]); //now就是i比lst大的时刻
            if (now<MIN || now==MIN && rk[i]>rk[who]) MIN=now,who=i;
            //找到最近的需要更新lst的位置
        }
        if (who && rk[i]>rk[who]){ //同理针对who进行更新
            int now=i+LCP(rk[who],rk[i]);
            if (now<nxtMIN || now==nxtMIN && rk[i]>rk[nxtwho]) nxtMIN=now,nxtwho=i;
            //找到最近的需要更新who的位置
        }
        if (i==MIN){ //当i到达MIN时，当前最优解更新为lst
            lst=who;MIN=1e9;who=0;
            if (nxtwho) MIN=nxtMIN,who=nxtwho,nxtMIN=1e9,nxtwho=0;
            //将MIN和who修正为nxtMIN和nxtwho，避免漏掉更新信息
        }
        printf("%d %d\n",lst,i);
    }
    return 0;
}