首页 > 代码库 > 后缀数组（基数排序）的具体分析

后缀数组（基数排序）的具体分析

2024-07-17 12:34:59   215人阅读

我看后缀数组，思想很容易懂，但是基数排序那边我确实理解了很久才理解，现在我写一份自己可以看懂的具体分析。

第一步，首先将所有的位置上的值装入数组中，并记录排名为i的数为sa[i],第i个数的排名为rank[i].

下面就要进行logn次的倍增操作，我们定义k为当前倍增长度

基数排序，痛苦ing

首先将每一对数的排名存到cur数组，cur[i][0]记录初始位置的排名，cur[i][1]为i+k位置上的排名

首先我们对第二关键字也就是cur[i][1]进行排名，用sa数组记录排名为i的在第几个

接下来，我们就对第一关键字进行排序，注意加入顺序为sa数组，这样可以保证，第一关键字一定时，排名小的一定在前面，从而保证了排序顺序，然后再按第一关键字进行加入。用链表处理会更容易懂一些

只能说白书上的代码真心看不懂，我对某位同学的程序加了一下注释，应该可以看懂。

 1 void Suffix_Array() 2 { 3     N++; 4     rep(i, 0, N - 1) SA[i] = i;//初始排名  5     sort(SA, SA + N, cmp);//根据位置排序  6     rep(i, 1, N - 1) Rank[SA[i]] = (s[SA[i]] > s[SA[i - 1]]) ? i : Rank[SA[i - 1]];//记录每个点的排名  7     for (int k = 1; ; k <<= 1)//枚举长度  8     { 9         rep(i, 0, N - 1) Cur[i][0] = Rank[i], Cur[i][1] = (i + k < N) ? Rank[i + k] : 0;//每一对点的排名 10         rep(i, 0, N) E[i].clear();11         rep(i, 0, N - 1) E[Cur[i][1]].push_back(i);//将所有排名一样的点加入链表 12         for (int i = N, n = 0; i >= 0; --i)13             for (int j = E[i].size() - 1; j >= 0; --j) SA[n++] = E[i][j];  //重新排名,大的在前，小的在后 14         rep(i, 0, N) E[i].clear();15         rep(i, 0, N - 1) E[Cur[SA[i]][0]].push_back(SA[i]);//加入当前点的排名，保证排名小的在后面 16         for (int i = 0, n = 0; i <= N; ++i)17             for (int j = E[i].size() - 1; j >= 0; --j) SA[n++] = E[i][j];//最终排名 18         //memset(Rank, 0, sizeof(Rank));19         int Indep = 1;20         rep(i, 1, N - 1)21             if (Cur[SA[i]][0] == Cur[SA[i - 1]][0] && Cur[SA[i]][1] == Cur[SA[i - 1]][1])22                 Rank[SA[i]] = Rank[SA[i - 1]], Indep = 0; else Rank[SA[i]] = i;//重新排名 23         if (Indep) break;24     }25 }
View Code

 


联系
我们