首页 > 代码库 > 后缀数组之最长公共前缀

后缀数组之最长公共前缀

2024-11-05 16:37:39   208人阅读

#include<stdio.h>
#define maxn 100
int main()
{
    int rank[maxn],height[maxn],sa[maxn]= {0,3,1,4,2},s[maxn]= {1,2,3,2,3};//s串可以看成abcbc
    int i,j,k=0;
    for(i=0; i<5; i++)
        rank[sa[i]]=i;
    for(i=0; i<5; i++)
    {

        if(rank[i]==0)//当rank[i]=0的时候也就是求height[0]没有意义所以直接把height[0]=0,k也变为0就行了
        {
            k=0;
            height[0]=0;
            continue;
        }
        if(k)
            k--;
        j=sa[rank[i]-1];
        /*
            当rank[k]不等于0的时候，rank[i]-1计算出的是上一个排名,通过sa数组找出上一个排名的起始坐标
        */
        printf("%d %d %d\n",rank[i],i,j);
        while(s[i+k]==s[j+k])
            k++;
            /*
            仔细体会i和j的关系还有后缀i控制的字符的个数
            上面的while循环其实是当k=0的时候才进行的当排完循序后后缀k和后缀i-1相邻即（排在后缀i-1的前一个的是后缀k），后缀k
            和后缀i-1分别删除首字符之后得到后缀k+1和后缀i，因此后缀k+1一定排在后缀i的前面(相邻),并且最长公共前缀长度为后缀k和
            后缀k和后缀i-1的最长公共前缀-1即h[i-1]-1举个例子：
            字符串abcbc的后缀为：
           0     abcbc
           1     bcbc
           2     cbc
           3     bc
           4     c
           排完序后为
           0     abcbc
           3     bc
           1     bcbc
           4     c
           2     cbc
           当i等于0的时候rank[0]所以height[0]等于0,k=0
           当i等于1的时候rank[1]为2,rank[1]-1==1,这个时候比较的是bcbc和排在他前面的后缀bc(i控制的bcbc的下标,j控制的bc的下标),经过while()循环
           判断出来的是k=2即最长公共前缀为2
           当i等于2的时候rank[2]为4，rank[2]-1==3,这个时候比较的是cbc和排在他前面的后缀c(bcbc和bc都是由i等于1的两个后缀都去掉一个b之后得到的，
           这个时候我们就没有必要再去计算了，我们可以直接通过bcbc和bc的最长公共前缀k减去1得到而没必要在去计算了）
           当i等于3的时候rank[3]为1，rank[1]-1==0,这个时候比较的是bc和排在他前面的后缀abcbc经过while()循环判断最长公共前缀为0
           当i等于4的时候rank[4]为3，rank[4]-1==2,这个时候比较的是c和排在他前面的后缀bc经过while()循环判断最长公共前缀为0
           有上述可以总结出当i是由0-n-1所以后缀是由长到短的，又因为当两个串排好序后相邻的时候，都去掉前面的一个后还是相邻的所以我们可以有长的
           递推出短的
            */
        height[rank[i]]=k;
    }
    for(i=0; i<5; i++)
        printf("%d ",height[i]);
    puts("");
    return 0;
}

后缀数组之最长公共前缀


联系
我们