首页 > 代码库 > 后缀数组之最长公共前缀
后缀数组之最长公共前缀
#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;
}
#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;
}
后缀数组之最长公共前缀
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。