2020牛客暑期多校训练营（第一场）A. B-Suffix Array

做法

对于字符串的第 $i$ 个字符，定义对偶函数 $b'(i)$ ，其含义为：对于原串的第 $i$ 个字符，找到它之后与它相同的字符位置 $j$ ，结果的第 $i$ 个元素即为 $j-i$ 。如果不存在这样的字符，相应的结果为 $\infty$ 。
就像题中的函数 $B$ ，一个字符串的函数 $B'$ 就是由每个位置的 $b'$ 组成。
定义 $B'$ 上的小于关系为字典序从大到小，并且前缀优先。

举例：
$B'(a)=(\infty)<B'(ab)=(\infty,\infty)<B'(aba)=(2,\infty,\infty)$

按照对偶函数的顺序构造后缀数组即可。

举例：
以串 abaabaaaabba 为例：

$rank[i]$ $i$ $s[i:n]$ $B(s[i:n])$ $LCP[i]$ $B'(s[i:n])$ $LCP[B'(i)]$

$1$ $12$ a $0$ $-1$ $\infty$ $-1$

$2$ $11$ ba $0,0$ $1$ $\infty,\infty$ $1$

$3$ $5$ baaaabba $0,0,1,1,1,5,1,3$ $2$ $5,1,1,1,3,1,\infty,\infty$ $0$

$4$ $9$ abba $0,0,1,3$ $3$ $3,1,\infty,\infty$ $0$

$5$ $2$ baabaaaabba $0,0,1,3,2,1,1,1,5,1,3$ $4$ $3,1,2,5,1,1,1,3,1,\infty,\infty$ $2$

$6$ $4$ abaaaabba $0,0,2,1,1,1,5,1,3$ $2$ $2,5,1,1,1,3,1,\infty,\infty$ $0$

$7$ $1$ abaabaaaabba $0,0,2,1,3,2,1,1,1,5,1,3$ $4$ $2,3,1,2,5,1,1,1,3,1,\infty,\infty$ $1$

$8$ $10$ bba $0,1,0$ $1$ $1,\infty,\infty$ $0$

$9$ $8$ aabba $0,1,0,1,3$ $3$ $1,3,1,\infty,\infty$ $1$

$10$ $3$ aabaaaabba $0,1,0,2,1,1,1,5,1,3$ $3$ $1,2,5,1,1,1,3,1,\infty,\infty$ $1$

$11$ $7$ aaabba $0,1,1,0,1,3$ $2$ $1,1,3,1,\infty,\infty$ $1$

$12$ $6$ aaaabba $0,1,1,1,0,1,3$ $3$ $1,1,1,3,1,\infty,\infty$ $2$

答案即为列 $i$ 。

$rank[i]$	$i$	$s[i:n]$	$B(s[i:n])$	$LCP[i]$	$B'(s[i:n])$	$LCP[B'(i)]$
$1$	$12$	a	$0$	$-1$	$\infty$	$-1$
$2$	$11$	ba	$0,0$	$1$	$\infty,\infty$	$1$
$3$	$5$	baaaabba	$0,0,1,1,1,5,1,3$	$2$	$5,1,1,1,3,1,\infty,\infty$	$0$
$4$	$9$	abba	$0,0,1,3$	$3$	$3,1,\infty,\infty$	$0$
$5$	$2$	baabaaaabba	$0,0,1,3,2,1,1,1,5,1,3$	$4$	$3,1,2,5,1,1,1,3,1,\infty,\infty$	$2$
$6$	$4$	abaaaabba	$0,0,2,1,1,1,5,1,3$	$2$	$2,5,1,1,1,3,1,\infty,\infty$	$0$
$7$	$1$	abaabaaaabba	$0,0,2,1,3,2,1,1,1,5,1,3$	$4$	$2,3,1,2,5,1,1,1,3,1,\infty,\infty$	$1$
$8$	$10$	bba	$0,1,0$	$1$	$1,\infty,\infty$	$0$
$9$	$8$	aabba	$0,1,0,1,3$	$3$	$1,3,1,\infty,\infty$	$1$
$10$	$3$	aabaaaabba	$0,1,0,2,1,1,1,5,1,3$	$3$	$1,2,5,1,1,1,3,1,\infty,\infty$	$1$
$11$	$7$	aaabba	$0,1,1,0,1,3$	$2$	$1,1,3,1,\infty,\infty$	$1$
$12$	$6$	aaaabba	$0,1,1,1,0,1,3$	$3$	$1,1,1,3,1,\infty,\infty$	$2$
答案即为列 $i$ 。

证明

详细证明见论文 Parameterized Suffix Arrays for Binary Strings。以下大致描述该论文的思路。

我们只需证明， $B$ 与 $B'$ 存在对应的偏序关系。即

$\begin{aligned} B'(s[i:n])<B'(s[j:n]) \Rightarrow B(s[i:n])<B(s[j:n]) \\ B'(s[i:n])=B'(s[j:n]) \Rightarrow B(s[i:n])=B(s[j:n]) \end{aligned}$

那么 $B'(s[i:n])=B'(s[j:n])$ 时显然。下面考虑小于的情况。

如果 $B'(s[i:n])$ 是 $B'(s[j:n])$ 的前缀，那么 $s[i:n]$ 要么是 $s[j:n]$ 的前缀，要么把所有 $s[i:n]$ 中的 $a,b$ 互相代换之后是 $s[j:n]$ 的前缀。反之亦然。

证明：
反证。不妨设 $s_i[k]=s[i+k]=s[n],s_j[k]=s[j+k] \not = s[n]$
那么 $b'_i(k),b'_i(b'_i(k)),\dots$ 中必然有一个为 $n$ ， $b'_j(k),b'_j(b'_j(k)),\dots$ 中必然没有 $n$ 。
与「 $B'(s[i:n])$ 是 $B'(s[j:n])$ 的前缀」相矛盾。
另一侧的证明显然。

由此，显然对于任意的 $k$ ，要么 $b_i(k)=b_j(k)$ ，要么 $b_i(k)=0$ 。即 $B(s[i:n])$ 要么是 $B(s[j:n])$ 的前缀，要么存在 $b_i(k)=0<b'_j(k)$ 。
如果 $B'(s[i:n])$ 不是 $B'(s[j:n])$ 的前缀。那么必然存在 $s[i+k] \not = s[j+k]$ 。
记满足 $s[i]=s[i+1]= \cdots =s[i+k-1] \not = s[i+k]$ 的串为 $a(k)b$ ，满足 $s[i]=s[i+1]= \cdots =s[i+k-1]=s[i+k]=s[n]$ 的串为 $a(k)x$ 。
存在如下没有前缀关系的情况（以下假设 $i<j$ ）：
- $a(i)b$ 与 $a(j)b$
  
  pos 1 2 $\cdots$ i-1 i i+1
  
  $B(a(i)b)$ 0 1 $\cdots$ 1 1 0
  
  $B(a(j)b)$ 0 1 $\cdots$ 1 1 1
  
  $B'(a(i)b)$ 1 1 $\cdots$ 1 sth>1 or $\infty$ sth
  
  $B'(a(j)b)$ 1 1 $\cdots$ 1 1 1 or sth
  
  可知 $B(a(i)b)<B(a(j)b),B'(a(i)b)<B'(a(j)b)$
- $a(i)b$ 与 $a(j)x$
  
  pos 1 2 ... i-1 i i+1
  
  $B(a(i)b)$ 0 1 ... 1 1 0
  
  $B(a(j)x)$ 0 1 ... 1 1 1
  
  $B' (a(i)b)$ 1 1 ... 1 sth>1 or $\infty$ sth
  
  $B' (a(j)x)$ 1 1 ... 1 1 1 or x
  
  可知 $B(a(i)b)<B(a(j)x),B'(a(i)b)<B'(a(j)x)$

pos	1	2	$\cdots$	i-1	i	i+1
$B(a(i)b)$	0	1	$\cdots$	1	1	0
$B(a(j)b)$	0	1	$\cdots$	1	1	1
$B'(a(i)b)$	1	1	$\cdots$	1	sth>1 or $\infty$	sth
$B'(a(j)b)$	1	1	$\cdots$	1	1	1 or sth

pos	1	2	...	i-1	i	i+1
$B(a(i)b)$	0	1	...	1	1	0
$B(a(j)x)$	0	1	...	1	1	1
$B' (a(i)b)$	1	1	...	1	sth>1 or $\infty$	sth
$B' (a(j)x)$	1	1	...	1	1	1 or x

综上，原命题得证。

时间复杂度

视后缀数组的构造算法， $O(n \log n)$ 到 $O(n)$

实现细节

通过令 $\infty=n$ ，并且加入虚节点 $b'[n+1]>n$ 的方式，通过普通后缀数组模板实现排序。

代码

#include <bits/stdc++.h>

using namespace std;

const int N=3000020;

char ts[N];
int s[N];
int n,sa[N],rk[N],oldrk[N << 1],id[N],px[N],cnt[N];

bool cmp(int x,int y,int w) 
{
    return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
}

void solve()
{
    int l[2]={n+1,n+1};
    for(int i=n;i>0;i--)
    {
        s[i]=((l[ts[i]-'a']>n?n:l[ts[i]-'a']-i));
        l[ts[i]-'a']=i;
    }
    n++;
    s[n]=n;
    int i,m=n+3,p,w;

    for(int i=0;i<=n+5;i++)
    {
        sa[i]=rk[i]=oldrk[i]=oldrk[i+n+5]=id[i]=px[i]=cnt[i]=0;
    }

    for(i=1;i<=n;++i) ++cnt[rk[i]=s[i]];
    for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
    for(i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;

    for(w=1;w<n;w<<=1,m=p) 
    { 
        for(p=0,i=n;i>n-w;--i) id[++p]=i;
        for(i=1;i<=n;++i) if(sa[i]>w) id[++p]=sa[i]-w;
        for(i=0;i<=n;++i) cnt[i]=0;
        for(i=1;i<=n;++i) ++cnt[px[i]=rk[id[i]]];
        for(i=1;i<=m;++i) cnt[i]+=cnt[i-1];
        for(i=n;i>=1;--i) sa[cnt[px[i]]--]=id[i];
        for(i=0;i<=min(N-1,2*n+5);++i) oldrk[i]=rk[i];

        for(p=0,i=1;i<=n;++i) rk[sa[i]]=cmp(sa[i],sa[i-1],w)?p:++p;
    }

    for(i=n-1;i>=1;--i) printf("%d ",sa[i]);
    printf("\n");
}

int main(void)
{
    while(~scanf("%d",&n))
    {
        scanf("%s",ts+1);
        solve();
    }

    return 0;
}