首页 > 基础算法 > 字符串处理 > 后缀数组及应用
2014
10-08

后缀数组及应用

后缀数组

建议先了解下后缀树:后缀树简介

在字符串处理当中,后缀树和后缀数组都是非常有力的工具,其中后缀树大家了解得比较多,关于后缀数组则很少见于国内的资料。其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树容易编程实现,能够实现后缀树的很多功能而时间复杂度也不太逊色,并且,它比后缀树所占用的空间小很多。

后缀树组是一个字符串的所有后缀的排序数组。后缀是指从某个位置 i 开始到整个串末尾结束的一个子串。字符串 r 的从 第 i 个字符开始的后缀表示为 Suffix(i) ,也就是Suffix(i)=r[i..len(r)] 。

例子:

字符串: "banana"的所有后缀如下:

0 banana                          5 a
1 anana     对所有后缀排序        3 ana
2 nana      ---------------->     1 anana  
3 ana        字典序               0 banana  
4 na                              4 na   
5 a                               2 nana

所以 "banana" 的后缀数组SA为: {5, 3, 1, 0, 4, 2}

名次数组:名次数组Rank[i]保存的是以i开头的后缀的排名,与SA互为逆。简单的说,后缀数组是“排在第几的是谁”,名次数组是“你排第几”。

构造算法

求解后缀数组的算法主要有两种:倍增算法DC3算法。在这里使用的是许智磊的倍增算法,复杂度为nlogn。关于详细求解后缀数组的算法,详见许智磊2004国家集训队论文

这里只给出最直接的求解算法,就是先求得所有的后缀子串,再进行一次排序。

// 朴素的后缀树组构造算法
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

// 表示一个后缀,index是后缀的开始下标位置
struct suffix
{
    int index;
    char *suff;
};

// 字典序比较后缀
int cmp(struct suffix a, struct suffix b)
{
    return strcmp(a.suff, b.suff) < 0? 1 : 0;
}

// 构造txt的后缀数组
int *buildSuffixArray(char *txt, int n)
{
    //结果
    struct suffix suffixes[n];

    for (int i = 0; i < n; i++)
    {
        suffixes[i].index = i;
        suffixes[i].suff = (txt+i);
    }

    // 排序
    sort(suffixes, suffixes+n, cmp);

    // 排在第几的是谁
    int *suffixArr = new int[n];
    for (int i = 0; i < n; i++)
        suffixArr[i] = suffixes[i].index;

    return  suffixArr;
}

//打印
void printArr(int arr[], int n)
{
    for(int i = 0; i < n; i++)
        cout << arr[i] << " ";
    cout << endl;
}

int main()
{
    char txt[] = "banana";
    int n = strlen(txt);
    int *suffixArr = buildSuffixArray(txt,  n);
    cout << "Following is suffix array for " << txt << endl;
    printArr(suffixArr, n);
    return 0;
}

输出:

Following is suffix array for banana
5 3 1 0 4 2

上面算法的实际复杂度为O(n2Logn),虽然排序的复杂度为O(nLogn) ,但是后缀之间的比较复杂度为 O(n)。

如何利用后缀数组来匹配字符串?

在回到那个经典的字符串匹配问题,如何在text中查找模式串pattern?有了后缀数组,我们就可以用二分查找来进行搜索。下面是具体的算法:

void search(char *pat, char *txt, int *suffArr, int n)
{
    int m = strlen(pat);  

    int l = 0, r = n-1;  
    while (l <= r)
    {
        // 查看 'pat'是否是中间的那个后缀的前缀字串
        int mid = l + (r - l)/2;
        int res = strncmp(pat, txt+suffArr[mid], m);

        if (res == 0)
        {
            cout << "Pattern found at index " << suffArr[mid];
            return;
        }
        if (res < 0) r = mid - 1;
        else l = mid + 1;
    }
    cout << "Pattern not found";
}

int main()
{
    char txt[] = "banana";  // text
    char pat[] = "nan";   // 模式串

    // 构造后缀数组
    int n = strlen(txt);
    int *suffArr = buildSuffixArray(txt, n);

    // 在txt中搜索pat是否出现
    search(pat, txt, suffArr, n);
    return 0;
}

输出:

Pattern found at index 2

上面这个搜索算法的复杂度为O(mLogn),其实还有更高效的基本后缀数组的算法,后续再做讨论。

后缀数组的应用

先定义height数组,height[i] = suffix(SA[i-1])和suffix(SA[i])的最长公共前缀,也就是排名相邻的两个后缀的最长公共前缀。

suffix-array

例1:最长公共前缀
给定一个串,求任意两个后缀的最长公共前缀。
解:先根据rank确定这两个后缀的排名i和j(i<j),在height数组i+1和j之间寻找最小值。(可以用rmq优化)

例2:最长重复子串(不重叠)(poj1743)
解:二分长度,根据长度len分组,若某组里SA的最大值与最小值的差>=len,则说明存在长度为len的不重叠的重复子串。

例3:最长重复子串(可重叠)
解:height数组里的最大值。这个问题等价于求两个后缀之间的最长公共前缀。

例4:至少重复k次的最长子串(可重叠)(poj3261)
解:二分长度,根据长度len分组,若某组里的个数>=k,则说明存在长度为len的至少重复k次子串。

例5:最长回文子串(ural1297)
给定一个串,对于它的某个子串,正过来写和反过来写一样,称为回文子串。
解:枚举每一位,计算以这个位为中心的的最长回文子串(注意串长要分奇数和偶数考虑)。将整个字符串反转写在原字符串后面,中间用$分隔。这样把问题转化为求某两个后缀的最长公共前缀。

例6:最长公共子串(poj2774)
给定两个字符串s1和s2,求出s1和s2的最长公共子串。
解:将s2连接到s1后,中间用$分隔开。这样就转化为求两个后缀的最长公共前缀,注意不是height里的最大值,是要满足sa[i-1]和sa[i]不能同时属于s1或者s2。

例7:长度不小于k的公共子串的个数(poj3415)
给定两个字符串s1和s2,求出s1和s2的长度不小于k的公共子串的个数(可以相同)。
解:将两个字符串连接,中间用$分隔开。扫描一遍,每遇到一个s2的后缀就统计与前面的s1的后缀能产生多少个长度不小于k的公共子串,这里s1的后缀需要用单调栈来维护。然后对s1也这样做一次。

例8:至少出现在k个串中的最长子串(poj3294)
给定n个字符串,求至少出现在n个串中k个的最长子串。
将n个字符串连接起来,中间用$分隔开。二分长度,根据长度len分组,判断每组的后缀是否出现在不小于k个原串中。

参考:http://yzmduncan.iteye.com/blog/979771

http://www.geeksforgeeks.org/suffix-array-set-1-introduction/


  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

  3. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  4. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience