吉隆坡建设大学中文网站,郴州市官网入口,征婚网站开发,网页美工设计ppt为什么一开始要再字符串末尾多算个0呢 因为当开始分关键字比较的时候 最后要组成两个 字符所以要多个0 什么你有问我为什么填0 因为0小啊 先处理呗 虽然 sa是根据每个字符确定的大小 也就是排布的每个字符的排名 但是在初次求第二关键字排序的时候 可以使用sa的结论 首…为什么一开始要再字符串末尾多算个0呢 因为当开始分关键字比较的时候 最后要组成两个 字符所以要多个0 什么你有问我为什么填0 因为0小啊 先处理呗 虽然 sa是根据每个字符确定的大小 也就是排布的每个字符的排名 但是在初次求第二关键字排序的时候 可以使用sa的结论 首先吧sa后面的0排到最前面 那么0的数量 也就是从n-j到n开区间 都是0作为第二关键字的区域 也就是这句话
for(p0,in-j;in;i) y[p]i;
这一句
for(int i0;in;i)if(sa[i]j)y[p]sa[i]-j;
是表示 当0已经排完了 现在再把非0的排进去 如何排进去呢 我们看 我们从1-n开区间枚举 如果sai大于等于j说明排到第i位的后缀的位置是大于等于j大于等于 现在的枚举长度的 那么就把他们放到y 也就是第二关键字排名数组中 并将其值记录为本字符串的开始位置sa[i]-j;
for(i0;in;i) wv[i]x[y[i]];
由于y数组中是按照第二关键字排序后存放的开始位置的数组 那么当我按照y从x数组中把值提取出来付给wv数组时 就相当于 把要比较的长度为2的倍增一倍的数组放到wv中去了 接下来就用下面的四个for循环来按第一关键字对合并后的字符串进行排序最后更新sa道理同上面对字符串第一个字符进行排序的四个for循环。 for(i0;im;i) ws[i]0;//将新的桶清0 1for(i0;in;i) ws[wv[i]];//2for(i1;im;i) ws[i]ws[i-1];//3for(in-1;i0;i--) sa[--ws[wv[i]]]y[i];//4
1盛放j1 长度为2 由于是按照低位排过序后的数组放入的wv 而wv存放的是第一关键字的值 为后续排序做准备 2按照第一关键字的顺序将其装桶标记 3按照第一关键字的顺序计算前缀和 4: 对于每个wv 是先按照第二关键字排序顺序装入的ws 也就是基数排序的本质 此时在2句又按照第一关键字的值存储的是第一关键字的值排好了序 每次– 逆序处理 此时得到的sa数组 就是一个在以第一二关键字合并的情况下按照其大小按照加上第一关键字的新顺序从高到低 讲y数组记录的是初始位置的值付给sa 表示字符串排序第i个位于y[i]
for(tx,xy,yt,p1,x[sa[0]]0,i1;in;i)x[sa[i]]cmp(y,sa[i-1],sa[i],j)?p-1:p;int cmp(int *r,int a,int b,int l){return r[a]r[b]r[al]r[bl];}一个cmp
最后再来看下cmp函数的作用 如果y也就是原来的x数组下a位置的和b位置的相等 并且第二关键字也相等 那么就会返回1 返回1就会让这段字符的实质排名为p-1 返回0表示不相等那么就说明两段不相等 让其等于p 则两段字符的排名相同 最终的p值 就代表我一共有排到了几 其中有可能有排名相等的项 那么这个p也就是其中下一循环的m值 也就是下一次循环 其中每个单关键字的排名不会超过m 存储到x数组中
魔板 #includeiostream
#includecstdio
#includealgorithm
#includecstring
#includevector
using namespace std;
typedef long long ll;
int n,m;
int *t,sa[1010],a[1010],b[1010],ms[1010],mv[1010];
char aa[50];
void LSD(int n,int *x,int *y,int *Ws,int *wv){m 130;for(int i0;im;i)Ws[i]0;for(int i0;in;i)Ws[x[i]aa[i]];for(int i1;im;i)Ws[i]Ws[i-1];for(int in-1;i0;i--)sa[--Ws[x[i]]]i;for(int p1,m,j1;pn;j1,mp){p0;for(int in-j;in;i)y[p]i;for(int i0;in;i)if(sa[i]j)y[p]sa[i]-j;for(int i0;in;i)wv[i]x[y[i]];for(int i0;im;i)Ws[i]0;for(int i0;in;i)Ws[wv[i]];for(int i1;im;i)Ws[i]Ws[i-1];for(int in-1;i0;i--)sa[--Ws[wv[i]]]y[i];int i;for(tx,xy,yt,p1,x[sa[0]]0,i1;in;i)x[sa[i]] (y[sa[i-1]]y[sa[i]]y[sa[i-1]j]y[sa[i]j]) ?p-1:p;}return;
}
int main()
{scanf(%s,aa);LSD(strlen(aa)1,a,b,ms,mv);for(int i0;istrlen(aa);i)printf(%d ,sa[i]);puts();return 0;
}
