【LZOJ3071】后缀数组/后缀树2

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
又是一篇模板题的总结

1

题解

知识点：

后缀数组，最长公共前缀

分析：

这道题是一道lcp的入门题，主要是先求出SA，然后通过SA线性求出Height，最后预处理出ST表，然后每次访问的时候调用即可。细节较多，在代码中讲解。

时间复杂度：

求SA：$O(n\log_{2}n)$

求Height：$O(n)$

st表的预处理：$O(n\log_{2}n)$

单次回答：$O(1)$

总计：$O(n\log_{2}n)$

代码：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
 
const int maxn=100010;
int n,m=122,q,sa[maxn],rnk[maxn],height[maxn],y[maxn],c[maxn],f[maxn][30],val[maxn];//f数组是st表，开到2的30次方已足够，val是预处理的log值，可以加快运算
char s[maxn];
 
void sort()
{
    int i;
    memset(c,0,sizeof(c));
    for (i=1;i<=n;i++)
        c[rnk[i]]++;
    for (i=2;i<=m;i++)
        c[i]+=c[i-1];
    for (i=n;i>=1;i--)
        sa[c[rnk[y[i]]]--]=y[i];
}
 
void getsa()
{
    int p=0,i,k;
    for (i=1;i<=n;i++)
    {
        rnk[i]=s[i]-96;//注意rnk一定要为正整数，否则会re、wa
        y[i]=i;
    }
    sort();
    for (k=1;p<n;m=p,k<<=1)
    {
        p=0;
        for (i=n-k+1;i<=n;i++)
            y[++p]=i;
        for (i=1;i<=n;i++)
            if (sa[i]>k)
                y[++p]=sa[i]-k;
        sort();
        swap(rnk,y);
        rnk[sa[1]]=p=1;
        for (i=2;i<=n;i++)
            rnk[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k])?p:++p;
    }
}
 
void getheight()
{
    int i,j,k=0;/*
    for (i=1;i<=n;i++)
        rnk[sa[i]]=i;*/
    for (i=1;i<=n;i++)
    {
        if (k)
            k--;
        j=sa[rnk[i]-1];
        while (s[j+k]==s[i+k])
            k++;
        height[rnk[i]]=k;
    }
}
 
void init()
{
    int i,j;
    memset(f,0x3f,sizeof(f));//因为求min，所以要初始一个INF
    for (i=1;i<=n;i++)
        f[i][0]=height[i];
    for (j=1;j<=val[n];j++)//先枚举幂，再枚举位置
        for (i=1;i+(1<<j)-1<=n;i++)
            f[i][j]=min(f[i][j-1],f[i+(1<<j-1)][j-1]);//注意是j-1而不是j
}
 
int st(int l,int r)
{
    int k=val[r-l+1];
    return min(f[l][k],f[r-(1<<k)+1][k]);//一定要+1
}
 
int main()
{
    int i,j,k;
    scanf("%s",s+1);
    n=strlen(s+1);
    for (i=2;i<=n;i++)//要从2开始算
        val[i]=val[i>>1]+1;
    getsa();
    getheight();
    scanf("%d",&q);
    init();
    while (q--)
    {
        scanf("%d%d",&i,&j);
        if (rnk[i]>rnk[j])//如果排名是错的，那么先换位置
            swap(i,j);
        if (i==j)
            printf("%d\n",n-i+1); //一样就不用算了
        else
            printf("%d\n",st(rnk[i]+1,rnk[j]));//height[rnk[i]]表示的是rnk[i]与rnk[i]-1的LCP，不是计算的范围
    }
    return 0;
}
显示 Gitment 评论