(代码) 后缀数组+lcp的c++实现

suffix array后缀数组一般用于字符串匹配问题当中,一般来说可以用suffix tree解决的字符串匹配问题用suffix array都可以解决.

主要参考了geeksforgeeks上关于后缀数组和lcp(longest common prefix)的教程.

https://www.geeksforgeeks.org/suffix-array-set-2-a-nlognlogn-algorithm/

https://www.geeksforgeeks.org/%c2%ad%c2%adkasais-algorithm-for-construction-of-lcp-array-from-suffix-array/

自己封装了一个SuffixArray类,里面包含后缀数组和lcp.因为构造suffix array和lcp的代码量有些大,代码就贴在这里,以后万一需要用的时候可以直接拿来用...

struct Suffix{
    int _index;
    int _rank[2];
};

class SuffixArray{
public:
    vector<Suffix> getSuffixes(){return suffixes;}
    vector<int> getlcp(){return lcp;}

    //构建后缀数组
    void build(string& s);;
    static bool sortFunction(Suffix& a,Suffix& b);

private:
    void setstring(string& str);
    void buildlcp();
    void buildSuffixes();

    vector<Suffix> suffixes;//所有后缀
    vector<int> lcp;
    string s;
};

void SuffixArray::build(string& str){
    this->setstring(str);
    this->buildSuffixes();
    this->buildlcp();
}

bool SuffixArray::sortFunction(Suffix& a,Suffix& b){
    if(a._rank[0]<b._rank[0]) return true;
    else if(a._rank[0]>b._rank[0]) return false;
    else return a._rank[1]<b._rank[1];
}

void SuffixArray::buildSuffixes(){
    int n=(int)s.size();
    suffixes.resize(n);
    Suffix tmp;
    for(int i=0;i<n;++i){
        tmp._index=i;
        tmp._rank[0]=s[i]-'a';
        tmp._rank[1]=(i+1<n)?s[i+1]-'a':-1;
        suffixes[i]=tmp;
    }
    sort(suffixes.begin(),suffixes.end(),sortFunction);
    vector<int> suffix_map(n);

    //根据前k个字符对后缀进行排序
    int prev_rank0=suffixes[0]._rank[0],prev_rank1=suffixes[0]._rank[1];
    int curr_rank0,curr_rank1;
    suffixes[0]._rank[0]=0;

    //循环条件写成k<2*n而不是k<=n,否则为"aaaaaaa"这种字符串建立后缀数组的时候会出错
    for(int k=4;k<2*n;k*=2){
        for(int i=0;i<n;++i) suffix_map[suffixes[i]._index]=i;
        for(int i=1;i<n;++i){
            curr_rank0=suffixes[i]._rank[0],curr_rank1=suffixes[i]._rank[1];
            if(suffixes[i]._rank[0]==prev_rank0 && suffixes[i]._rank[1]==prev_rank1)
                suffixes[i]._rank[0]=suffixes[i-1]._rank[0];
            else
                suffixes[i]._rank[0]=suffixes[i-1]._rank[0]+1;
            prev_rank0=curr_rank0,prev_rank1=curr_rank1;
        }

        for(int i=0;i<n;++i){
            //后缀i的3~4个字符=后缀i+1的前两个字符
            int next_suffix=suffixes[i]._index+k/2;
            if(next_suffix>=n) suffixes[i]._rank[1]=-1;
            else suffixes[i]._rank[1]=suffixes[ suffix_map[next_suffix] ]._rank[0];
        }
        sort(suffixes.begin(),suffixes.end(),sortFunction);
    }
}


//后缀i的最长公共前缀为k 则后缀i+1的最长公共前缀至少为k-1
void SuffixArray::buildlcp(){
    int n=(int)suffixes.size();
    lcp.resize(n);
    vector<int> suffix_map(n);

    for(int i=0;i<n;++i){
        suffix_map[ suffixes[i]._index ]=i;
    }

    int pre_lcp=0;
    for(int i=0;i<n;++i){
        //后缀i的最长公共前缀
        //pre_lcp:后缀i-1的最长公共前缀
        int suffix_index=suffix_map[i];
        if(suffix_index==n-1){
            lcp[suffix_index]=0;
            continue;
        }
        int _next=suffixes[suffix_index+1]._index;
        //cout<<"i="<<i<<" _next="<<_next<<endl;

        if(pre_lcp==0){
            lcp[suffix_index]=0;
            for(int j=0;i+j<n && _next+j<n;++j){
                if(s[i+j]==s[_next+j]) ++lcp[suffix_index];
                else break;
            }
        }else{
            lcp[suffix_index]=pre_lcp-1;
            for(int j=pre_lcp-1;i+j<n && _next+j<n;++j){
                if(s[i+j]==s[_next+j]) ++lcp[suffix_index];
                else break;
            }
        }

        pre_lcp=lcp[suffix_index];
    }
}

void SuffixArray::setstring(string& str){
    s=str;
}