后缀数组

发表于 | 分类于 |

后缀数组基础(前置知识:计数排序)

虽然我很不喜欢char*,但是没找到string的板子,鉴于我是个懒狗,故本文中先使用char*版本模板,后续找到string版本会进行替换(注意char*版本中,下标均从1开始,应该是为了贴合第1小,第2小等概念)

首先,规定,后缀i的编号i是其首字符,在原字符串中的位置,如aaabccc,bccc的编号是4

sa[i]存储的是第i小的后缀编号

rk[i]存储的是编号为i的后缀的排名

故,明显有sa[rk[i]]=rk[sa[i]]=i

我们想要nlogn求出sa和rk

让我们将问题放宽,求出所有长度为w的子串的排序(若长度小于w,则后续补”最小字符”)

当w为1时,显然,可以O(n)求出

进一步拓展到w为2,则可利用w为1的结果,比如ab,其中a在w为1时排1,b在w为1时排2,则ab的权值为(1,2),可直接利用这个排名去比较

同理,w最多拓展logn次,拓展一次花费O(n),故总复杂度为O(nlogn),需要加一些常数优化

SA模板

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
namespace SA
{
    char s[maxn];
    ll sa[maxn], rk[maxn], oldrk[maxn << 1], id[maxn], px[maxn], cnt[maxn];
    ll i, m = 300, p, w, len,k;
    bool cmp(ll x, ll y, ll w)
    {
        return oldrk[x] == oldrk[y] && oldrk[x + w] == oldrk[y + w];
    }
    void init()
    {
        memset(cnt, 0, sizeof(cnt));
        len = strlen(s + 1);
        for (i = 1; i <= len; i++)
        {
            ++cnt[rk[i] = s[i]];
        }
        for (i = 1; i <= m; i++)
        {
            cnt[i] += cnt[i - 1];
        }
        for (i = len; i >= 1; i--)
        {
            sa[cnt[rk[i]]--] = i;
        }
        for (w = 1; w<len; w <<= 1, m = p)
        {
            p = 0;
            for (i = len; i > len - w; --i)
            {
                id[++p] = i;
            }
            for (i = 1; i <= len; ++i)
            {
                if (sa[i] > w)
                {
                    id[++p] = sa[i] - w;
                }
            }
            memset(cnt, 0, sizeof(cnt));
            for (i = 1; i <= len; i++)
            {
                ++cnt[px[i] = rk[id[i]]];
            }
            for (i = 1; i <= m; i++)
            {
                cnt[i] += cnt[i - 1];
            }
            for (i = len; i >= 1; i--)
            {
                sa[cnt[px[i]]--] = id[i];
            }
            memcpy(oldrk, rk, sizeof(rk));
            p = 0;
            for (i = 1; i <= len; i++)
            {
                rk[sa[i]] = cmp(sa[i], sa[i - 1], w) ? p : (++p);
                if (p == len)
                {
                    for (i = 1; i <= len; i++)
                    {
                        sa[rk[i]] = i;
                    }
                    break;
                }
            }
        }
    }
}

注意1:该模板中多次复用i,其中p=len时直接break了,故嵌套使用i不会出错

LCP:longest common prefix,最长公共前缀长度

如何求字符串的各个后缀之间的LCP?

现规定height[i]为排名为i的后缀,和排名为i-1的后缀之间的LCP(height[1]视为0)

有结论,height[rk[i]]>=height[rk[i-1]]-1

很容易直观证明,设后缀i-1是aAD(aA即为rk[i-1]和rk[i-1]-1的公共部分)

则后缀i是AD(大写表示多个字符)

所以存在一个后缀,其为aAC(其大小为rk[i-1]-1)

所以存在一个后缀,其为AC(其编号为sa[rk[i-1]-1]+1)

故AC和AD一定能形成一个长度为A的公共前缀

上代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
for(i=1,k=0;i<=len;i++)
        {
            if(rk[i]==0)
            {
                continue;
            }
            if(k)
            {
                k--;
            }
            while(s[i+k]==s[sa[rk[i]-1]+k])
            {
                k++;
            }
            height[rk[i]]=k;
        }

k最多减少n次,k不超过n,故k最多加2n次,复杂度为O(n)

height数组的应用

1.lcp(sa[i],sa[j])=min(height[i+1],….,height[j])

很容易理解,排名从i到j,一直保持不变的前缀便是sa[i]和sa[j]的最长公共前缀

注意从i+1开始遍历

于是求LCP变成了RMQ问题,使用st表等算法能优化成log级

2.比较字符串的子串大小关系

假设A=S[a…b],B=S[c…d]

先计算lcp(a,c),若lcp(a,c)>=min(|A|,|B|),则A,B之间,长的子串包含短的子串(也可能相等),故大小关系完全取决于子串长度

若lcp<min(|A|,|B|),则A,B之间的大小关系等价于后缀a和后缀c的大小关系(因为在A和B的长度范围内就已经决定了其后缀的大小关系,故两者等价)

综上,同求lcp,复杂度为log级

3.计算不同子串的数目

先上结论:

不同子串的数目为

总结：对子串的操作,转化成后缀的前缀来考虑

都是抄的oiwiki的qwq

https://oi-wiki.org/string/sa/#onlogn-%E5%81%9A%E6%B3%95