首页 > 编程语言 > 详细

【知识总结】后缀数组(Suffix_Array)

时间:2018-12-13 18:18:54      阅读:228      评论:0      收藏:0      [点我收藏+]

又是一个学了n遍还没学会的算法……

后缀数组是一种常用的处理字符串问题的数据结构,主要由\(sa\)\(rank\)两个数组组成。以下给出一些定义:

\(str\)表示处理的字符串,长度为\(len\)。(下标从\(0\)开始)

\([i,j)\)表示\(str\)\(i\)\(j - 1\)的字串。

后缀\(i\)表示子串\([i,len)\),以字典序排序。

\(sa[i]\)表示排名为\(i\)的后缀的起始位置(即后缀\(sa[i]\)是第\(i\)名)

\(rank[i]\)表示后缀\(i\)的排名(从\(0\)开始)。显然\(rank[sa[i]]=i\)

一、基数排序

先简单介绍一下后缀数组的前置技能:基数排序。

以对整数数组\(arr\)排序为例。从低到高遍历每一个十进制位,对于每个位:

\(1.\)\(arr\)数组已经按照前\(i-1\)位排好序,(\(i=0\)时忽略这句),现在我们将把它变为按前\(i\)位排好序。脑补以下整数的比较方式,现在应该把第\(i\)位作为第一关键字,前\(i-1\)位作为第二关键字。

\(2.\)统计第\(i\)位为数字\(a\)的数的数量,存入\(count[a]\)

\(3.\)\(count\)数组求前缀和,算出最后一个第\(i\)位为\(a\)的数在按照前\(i\)位排序后数组中的位置的下一个。这句表达比较鬼畜,看下面的例子。

比如,\(i\)位为\(0\)的有\(2\)个,为\(1\)的有\(1\)个,为\(2\)的有\(3\)个,第\(3\)步以后\(count\)\(\{2,3,6\}\),那么排序后\(arr[0]\)\(arr[1]\)的第\(i\)位为\(0\)\(arr[2]\)的第\(i\)位为\(1\)\(arr[3]\)\(arr[5]\)的第\(i\)位为\(2\)

\(4.\)逆序遍历\(arr\),按照上一步中算出的第\(i\)位为\(a\)的数排序后的位置逆序填充临时数组。两个均逆序保证了对于第\(i\)位相同的数按照最初在\(arr\)中的位置排序。

\(5.\)最后,把临时数组复制给\(arr\),此时\(arr\)按照前\(i\)位有序。

int count[10];
for(int i = 1; i <= 10; i++, ra *= 10)
{
    memset(count, 0, sizeof(count));
    for (int j = 1; j <= n; j++)
        ++count[arr[j] / ra % 10];//step 2
    for (int j = 1; j < 10; j++)
        count[j] += count[j - 1];//step 3
    for(int j = n - 1; j >= 0; j--)
        buc[--count[arr[j] / ra % 10]] = arr[j];
    memcpy(arr, buc, sizeof(int[n]));
}

二、倍增构造后缀数组

考虑我们现在有了对所有形如\([i,min(i+tmp,len))\)的子串排序的数组\(sa\)\(rank\)(对于相同的子串,它们的\(rank\)值相同,在\(sa\)中顺序任意),我们现在要构造对所有形如\([i,min(i+2tmp,len))\)的子串排序。最坏情况下,当\(2tmp\geq len\)时就得到了答案。

可以发现此时很类似于基数排序时排到某一位时的情况。此时,第一关键字是\([i,i+tmp)\),第二关键字是\([i+tmp, i+2tmp)\)。并且,现在已经按照第二关键字排好序了。

于是我们先看看此处的基数排序。其中\(kind\)\(rank\)中不同值的种数(由于\(rank\)\(0\)开始,也可以看成\(rank\)中最大值加\(1\)),\(tp[i]\)表示哪个串的第二关键字在所有第二关键字中的排名是\(i\)

void radix_sort()
{
    static int count[N];
    memset(count, 0, sizeof(int[kind]);
    for (int i = 0; i < len; i++)
        count[rank[tp[i]]]++;
    for (int i = 1; i < kind; i++)
        count[i] += count[i - 1];
    for (int i = len - 1; i >= 0; i--)
        sa[--count[rank[tp[i]]]] = tp[i];
}

然后我们来构造\(tp\)数组。首先,对于起点在\([len-tmp,len)\)中的串,它们的第二关键字都是空串,排名是最低的。所以它们应当在\(tp\)的开头:

for (int i = len - tmp; i < len; i++)
    tp[cnt++] = i;

然后,按照\(sa\)加入剩下的串。注意只有起点在\(tmp\)及以后的串才能作为第二关键字。

for(int i=0;i<len;i++)
    if(sa[i]>=tmp)
        tp[cnt++]=sa[i]-tmp;

至此,\(tp\)数组构造完毕,可以进行基数排序。排序后,我们要按照新的\(sa\)和旧的\(rank\)构造新的\(rank\)。首先,把旧的\(rank\)进行拷贝。为了优化常数可以这样写:

swap(rank,tp)

记住,此后\(tp\)就只是旧的\(rank\)的一份拷贝了,没有更多实际意义。更新\(rank\)的过程比较显然。

rank[sa[0]] = 0;
kind = 1;
for (int i = 1; i < len; i++)
{
    if (tp[sa[i]] == tp[sa[i - 1]] && 
        (sa[i] + tmp < len && sa[i - 1] + tmp < len) && 
        (tp[sa[i] + tmp] == tp[sa[i - 1] + tmp]))
        rank[sa[i]] = rank[sa[i - 1]];
    else
        rank[sa[i]] = kind++;
}

最后,如果\(kind=len\),即\(rank\)已经两两不同,则说明已经得出了答案。

三、应用:构造\(height\)数组

我不会,你开心不qwq

四、完整代码:

int sa[N], rank[N], tp[N], kind, len;
void radix_sort()
{
    static int count[N];
    memset(count, 0, sizeof(int) * kind);
    for (int i = 0; i < len; i++)
        count[rank[tp[i]]]++;
    for (int i = 1; i < kind; i++)
        count[i] += count[i - 1];
    for (int i = len - 1; i >= 0; i--)
        sa[--count[rank[tp[i]]]] = tp[i];
}
void build(const string &s)
{
    len = s.size();
    for (int i = 0; i < len; i++)
        rank[i] = s[i], tp[i] = i;
    kind = CH;
    radix_sort();
    for (int tmp = 1; tmp < len; tmp *= 2)
    {
        int cnt = 0;
        for (int i = len - tmp; i < len; i++)
            tp[cnt++] = i;
        for (int i = 0; i < len; i++)
            if (sa[i] >= tmp)
                tp[cnt++] = sa[i] - tmp;
        radix_sort();
        swap(rank, tp);
        rank[sa[0]] = 0;
        kind = 1;
        for (int i = 1; i < len; i++)
        {
            if (tp[sa[i]] == tp[sa[i - 1]] && 
                (sa[i] + tmp < len && sa[i - 1] + tmp < len) && 
                (tp[sa[i] + tmp] == tp[sa[i - 1] + tmp]))
                rank[sa[i]] = rank[sa[i - 1]];
            else
                rank[sa[i]] = kind++;
        }
        if (kind == len)
            break;
    }
}

【知识总结】后缀数组(Suffix_Array)

原文:https://www.cnblogs.com/zyt1253679098/p/10115485.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!