noone___'s blog
0%

后缀数组一些题

发表于 更新于 分类于
《后缀数组——处理字符串的有力工具》论文题组+其他题

基础

P3809 【模板】后缀排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
const int N=1e6+100;
char s[N];
int sa[N],rk[N];//sa[i]:排名i的后缀的位置;rk[i]:第i个位置开始的后缀的排名.其中 rk[ sa[i] ]=i,sa[ rk[i] ]=i
int tp[N],tax[N];//tp[i]:基数排序的第二关键词排名为i的后缀的位置;tax[i]:辅助基数排序,i号元素(即，名次)出现的次数
int n,m=75;//m字符集大小
int height[N];//height[i]:lcp(sa[i],sa[i-1]):排名为i的后缀与排名i-1的后缀的最长公共前缀

namespace SA{
    inline void Rsort(){
        for(rei i=0;i<=m;++i) tax[i]=0;
        for(rei i=1;i<=n;++i) ++tax[ rk[i] ];
        for(rei i=1;i<=m;++i) tax[i]+=tax[i-1];
        for(rei i=n;i;--i) sa[ tax[ rk[ tp[i] ] ]/*第一关键词相同时，第二关键词较大的后缀的排名*/ -- /*枚举第二关键词，通过rk定位到第一关键词大侠大小*/]=tp[i];
    }
    inline void get_sa(){
        for(rei i=1;i<=n;++i) rk[i]=s[i]-'0'+1,tp[i]=i;
        Rsort();
        for(rei w=1,p=0;p<n;m=p,w<<1){//w:当前倍增的长度;当前已经求出长度w的后缀的排名，要更新长度2w的后缀的排名
            //p:不同的后缀个数.显然仅有原字符串后缀不同时,p=n,退出
            //m=p:对基数排序的优化，字符集大小就是排名的个数
            p=0;
            //此时sa[i]表示的是长度为w/2的后缀中排名i的位置,即,上一轮的结果
            for(rei i=1;i<=w;++i) tp[++p]=n-w+i;//一些没有第二关键字的后缀，其排名在最前面
            for(rei i=1;i<=n;++i) if(sa[i]>w) tp[++p]=sa[i]-w;
            Rsort();//上轮的rk更新本轮的sa
            swap(tp,rk);
            rk[ sa[1] ]=p=1;
            for(rei i=2;i<=n;++i) rk[ sa[i] ]=(tp[ sa[i-1] ]==tp[ sa[i] ] && tp[ sa[i-1]+w ]==tp[ sa[i]+w ]) ? p : ++p;//当两个后缀上一轮排名相同时,本轮也相同
        }
    }
    inline void get_he(){
        rei k=0;
        for(rei i=1;i<=n;++i){
            if(k) --k;
            rei j=sa[ rk[i]-1 ];
            while(s[i+k]==s[j+k]) ++k;
            height[ rk[i] ]=k;
            printf("%d\n",k);
        }
    }
}

int main(){
    scanf("%s",s+1); n=strlen(s+1);
    SA::get_sa();
    for(rei i=1;i<=n;++i) printf("%d%c",sa[i],i==n ? 10 : 32);
    getchar(),getchar();
    return 0;
}

应用

两个后缀的最大公共前缀 $\text{lcp}$

$\text{lcp}(x,y)=\min\{height_{x+1},height_{x+2},…,height_{y}\}$ , $\text{rmq}$ 维护， $O(1)$ 查询

可重叠最长重复子串

$height_{\max}$

不可重叠最长重复子串

见例题 $1$

本质不同的子串数量

枚举每一个后缀，第 $i$ 个的贡献为 $len-sa_i+1-height_i$

例题

P2743 [USACO5.1]乐曲主题Musical Themes

求不重叠的最长重复子串，两字符串相等当且仅当相同为值的两个字符差值一定(即经过转调)

显然联想到差分，即转化为差分数组下求相等的不重叠最大子串，而最大重复子串为 $height$ 数组中最大值

要求不重叠，对 $k$ 二分，转化为子串的存在问题

将 $height \geq k$ 的归为一组，若组内 $sa_{\max}-sa_{\min}\leq k$ 则存在

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
rk[i]=s[i]+1

inline bool valid(int k){
    rei MAX=-INF,MIN=INF;
    for(rei i=1;i<=n;++i){
        if(height[i]<k) MAX=-INF,MIN=INF;
        MAX=max(MAX,sa[i]),MIN=min(MIN,sa[i]);
        if(MAX-MIN>k) return true;
    }
    return false;
}

int main(){
    ....
    rei l=0,r=n;
    while(l<=r){
    // puts("here");
        rei mid=l+r>>1; valid(mid) ? (l=mid+1,ans=mid) : r=mid-1;
    }
    ...
}

P2852 [USACO06DEC]Milk Patterns G

至少出现 $k$ 次的最长重复子串

$k$ 次，相当于选择 $k$ 个后缀后求出它们的 $\text{lcp}$

由 $\text{lcp}_{i,j}=\min\{height[rk[i+1]],…height[rk[j]]\}$ 可知，$k$ 个后缀在 $rk$ 上一定连续

二分即可

1
2
3
4
5
6
7
inline bool valid(int now,int cnt=0){
    for(rei i=1;i<=n;++i){
        if(height[i]<now) cnt=0;
        if(++cnt>=k) return true;
    }
    return false;
}

SP694 DISUBSTR - Distinct Substrings

本质不同的子串数量

双倍经验SP705 SUBST1 - New Distinct Substrings

每个后缀的前缀对应一个子串，枚举 $i$ 会产生 $n-sa_i+1$ 个，但需要减去和上一个的 $\text{lcp}$ 即，$height_i$

注意多测的数据 $\text{clear}$ ，要重置 $m$

1
2
3
4
5
6
7
8
9
10
inline void clear(){
    for(rei i=1;i<=n+10;++i) sa[i]=rk[i]=tp[i]=tax[i]=height[i]=0;
    ans=0; m=300;
}

int main(){
    ...
    for(rei i=1;i<=n;++i) ans+=n-sa[i]+1-height[i];
    ...
}

URAL1297 Palindrome

求最长回文子串

将整个字符串反过来写在原字符串后，中间用特殊字符隔开，先求这个新字符串的莫两个后缀的最长公共前缀，再枚举每一位，计算以其为重心的最长回文子串，注意分奇偶讨论. $O(n\log n)$ 的后缀数组 $+$ $O(n)$ 的 $\text{RMQ}$

$\sout{O(n)的\text{Manacher}也好啊}$

注意： 插入的特殊字符为 $1$ 时：

由于 0 的 $\text{ACSII}$ 码值为 $48$

故会出现 rk[i]=1-48('0')+1 的情况，于是要改成如下：

for(rei i=1;i<=n;++i) rk[i]=s[i]-'0'+49,tp[i]=i;

qwq卡了一上午在这个了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
inline int lcq(int i,int j){
    rei l=rk[i],r=rk[j];
    if(l==r) return -INF;
    if(l>r) swap(l,r); ++l;
    rei k=log2(r-l+1);
    return min(st[l][k],st[ r-(1<<k)+1 ][k]);
}

int main(){
    ...
    for(rei i=1;i<=len;++i){
        rei odd=lcq(i,2*len+2-i);
        if(ans<2*odd-1) ans=2*odd-1,pos=i-odd+1;
        rei even=lcq(i,2*len+3-i);
        if(ans<2*even) ans=2*even,pos=i-even;
    }
    ...
}

UVA10298 Power Strings

求循环同构串的最小循环节/连续重复最小子串

$\sout{KMP:n\%(n-next[n])=0 \ ?\ \frac{n}{n-next[n]}\ :\ 1 }$

$\sout{Hash}$

枚举长度的约数 $k$ ，判断 $1$ 与 $k+1$ 的后缀的 $\text{lcp}$ 是否为 $n-k$

1
2
for(rei k=1;k<n;++k) if(n%k==0 && lcp(1,k+1)==n-k) ans=n/k,k=n;
printf("%d\n",!ans ? 1 : ans);

SP687 REPEATS - Repeats

重复次数最多的连续重复子串

枚举长度 $L$ ，求长度 $L$ 的子串最多能连续出现几次

显然可以出现一次，考虑出现至少 $2$ 次的情况。

以子串 $sub_s$ 在 $s$ 中连续出现 $2$ 次为例，$sub_s$ 一定包含字符 $s_0,s_L,s_{2L},…$ 中相邻的两个，设包含了字符 $s_{L\times i},s_{L\times (i+1)}$

那么看这两个字符往前往后各能匹配到多远，记录 $\frac{\max 长度}{L}$ 和 $sub_{s_1}$

1
2
3
4
5
6
7
8
9
10
11
12
13
for(rei L=1;(L<<1)<=n;++L)
    for(rei i=0;L*(i+1)+1<=n;++i){
        rei x=L*i+1,y=L*(i+1)+1;
        if(s[x]!=s[y]) continue;
        rei z=lcp(x,y);
        rei t1=y+z-1,t0=0;//t0最早能匹配到的点，t1最晚能匹配到
        for(rei j=0;j<=L-1;++j){//当前起始点不确定时真正循环节的第几个，所以向前找L个
            if(x-j<1 || s[x-j]!=s[y-j]) break;
            t0=x-j;
            rei now=((t1-t0+1)/L);
            if(now>ans || (now==ans && rk[t0]<rk[al])) ans=now,al=t0,ar=t0+now*L-1;
        }
    }

P5546 [POI2000]公共串

给定 $n(n\leq 10)$ 个字符串，求其最长公共子串

双倍经验SP1811 LCS - Longest Common Substring

三倍经验SP1812 LCS2 - Longest Common Substring II

四倍经验SP10570 LONGCS - Longest Common Substring

（逃

论文中给出了两个字符串的做法，多字符串能从中推出：

子串具有连续性，字符串的任何一个子串都是这个字符串某个后缀的前缀，求多个字符串的公共子串相当于求每个字符串后缀的最长公共前缀的最大值

首先要把所有字符串连在一起，之间用题目限定的字符集以外的字符分隔

那么问题转化为：在 $height$ 数组上找连续一段使这一段包含来自每个字符串的至少一个后缀，设满足条件的第 $i$ 个区间为 $[l_i,r_i]$ ，最后的答案就是 $\displaystyle{\max_{l_i\leq x\leq r_i}height_i}$

先考虑计算区间：双指针扫一遍，数组记录第 $i$ 个字符串的后缀出现过的次数

再考虑计算答案：类比滑动窗口，维护一个单调队列即可

复杂度 $O(\sum |S| \log\sum|S|)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
namespace color{
    inline void build(){ for(rei i=1;i<=cnt;++i) for(rei j=L[i];j<=R[i];++j) col[ rk[j] ]=i;}
    inline void add(int x){
        if(!col[x]) return ;
        ++num[ col[x] ];
        if(num[ col[x] ]==1) ++tot;
    }
    inline void del(int x){
        if(!col[x]) return ;
        --num[ col[x] ];
        if(!num[ col[x] ]) --tot;
    }
}

int main(){
    ...
    scanf("%d",&cnt);
    for(rei i=1;i<=cnt;++i){
        L[i]=n+1;
        scanf("%s",s+n+1); n+=strlen(s+1+n);
        R[i]=n;
        s[++n]=i+'0';
    }
    SA::get_sa(),SA::get_he();
    color::build(); color::add(1);
    for(rei i=2;i<=n;++i){
        while(head<tail && height[ q[tail] ]>=height[i]) --tail;
        q[++tail]=i; color::add(i);
        if(tot==cnt){
            while(tot==cnt && l<i) color::del(l++);
            color::add(--l);
        }
        while(head<tail && q[head]<=l) ++head;
        if(tot==cnt) ans=max(ans,height[ q[head] ]);
    }
    printf("%d\n",ans);
    ...
}

其他乱七八糟不想用SAM写的

P4248 [AHOI2013]差异

求 $\displaystyle{\sum_{1\leq i<j\leq n} i+j-2\times \text{lcp}(T_i,T_j)}$

原式:

$height$ 数组中 $[2,n]$ 内的每个区间给答案贡献区间最小值，单调栈即可

1
2
3
4
5
6
7
8
9
stk[top=1]=1;
for(rei i=2;i<=n;++i){
    while(top && height[ stk[top] ]>height[i]) R[ stk[top--] ]=i;
    L[i]=stk[top];
    stk[++top]=i;
}
while(top) R[ stk[top--] ]=n+1;
ans=(ll) (n-1)*n*(n+1)/2;
for(rei i=2;i<=n;++i) ans-=(ll) 2*(R[i]-i)*(i-L[i])*height[i];

P7409 SvT

求 $\displaystyle{\sum_{i,j\in \{E\},i<j} \text{lcp}(T_i,T_j)}$

这个类似于上面的内题，但这个是给定的点两两组合，而上一题是全部 $n$

类比上题中用 $height$ 将 $\text{lcp}$ 转化为 $RMQ$ 问题，并用单调栈求答案

考虑本题中是否能得到类似的 $h’$

$\sum t\leq 3\times 10^6$ 的范围与虚树类似，故进行类似虚树的转化：将给定的点按 $rk$ 排序去重，$h’_i=\text{lcp}(st[ a[i-1] ],st[ a[i] ])$ ，那么 $h’$ 与上题的 $height$ 由相同性质，单调栈即可

1
2
3
4
5
6
7
8
9
10
sort(a+1,a+1+q,cmp);
q=unique(a+1,a+1+q)-a-1;
for(rei i=q;i>=2;--i) a[i]=lcp(a[i-1],a[i]);
a[1]=0,stk[++top]=1;
for(rei i=2;i<=q;++i){
    while(top && a[i]<a[ stk[top] ]) R[ stk[top--] ]=i-1;
    L[i]=stk[top]+1,stk[++top]=i;
}
while(top) R[ stk[top--] ]=q;
for(rei i=2;i<=q;++i) ans+=(ll) a[i]*(R[i]-i+1)*(i-L[i]+1);