天水做网站的公司,重庆有哪些大型互联网公司,建设网站的账务处理,做设计的公司的网站文章目录前言解析后缀排序优化1#xff1a;基数排序优化2#xff1a;简化第一次排序优化3#xff1a;提前break完整代码LCP与height所谓后缀数组#xff0c;就是存储后缀的数组 #xff08;逃#xff09;
前言
为什么一个算法#xff0c;如此难以理解却依然是成为一个…
文章目录前言解析后缀排序优化1基数排序优化2简化第一次排序优化3提前break完整代码LCP与height所谓后缀数组就是存储后缀的数组 逃
前言
为什么一个算法如此难以理解却依然是成为一个成熟OIer不可回避的必修课 足以可见后缀家族功能的强大
首先由于其本身的性质后缀数组对字典序相关的问题十分擅长 同时由于 heightheightheight 数组的众多优秀性质它在处理公共串问题和 LCP 问题上也十分强大 我目前SA的题加起来也没做上十道所以这样的“总结”请选择性阅读
解析
后缀排序
P3809 【模板】后缀排序 给出一个字符串把所有后缀按照字典序排序 n≤106n\le10^6n≤106 考虑倍增 一开始子串长度为 111每个位置的排名 rkirk_irki 就是自己位置的字符 然后在已知长度为 www 的所有子串的排名的情况下以 rkiwrk_{iw}rkiw 为第二关键字rkirk_irki 为第一关键字排序可以得到长度为 2w2w2w 的所有子串的排名空串的排名视为负无穷 每次用 sort 的话时间复杂度 O(nlog2n)O(nlog^2n^)O(nlog2n)
优化1基数排序
注意到这里的排序是关于大小的排序且值域排名只有 O(n)O(n)O(n) 所以我们可以使用基数排序代替 sort时间复杂度变成 O(nlogn)O(nlogn)O(nlogn) 注意 基数排序重新排列的循环必须倒序枚举这样才能保证排序的稳定性 memset(cnt,0,sizeof(cnt));
memcpy(oldrk,rk,sizeof(rk));
for(int i1;in;i) cnt[rk[id[i]]];
for(int i1;im;i) cnt[i]cnt[i-1];
for(int in;i1;i--) sa[cnt[rk[id[i]]]--]id[i];
p0;
for(int i1;in;i){if(oldrk[sa[i]]oldrk[sa[i-1]]oldrk[sa[i]w]oldrk[sa[i-1]w]) rk[sa[i]]p;else rk[sa[i]]p;
}
mp;优化2简化第一次排序
第一次是关于rkiwrk_{i_w}rkiw 排序 并不需要基数排序只需要
p0;
for(int in;in-w;i--) id[p]i;
for(int i1;in;i){if(sa[i]w) id[p]sa[i]-w;
}即可
优化3提前break
玄学优化 大概就是不必真的倍增到总长度只需要让所有字符串的排名互相分开即可 这东西在全是 a 这样的串中可以说是等于没有但在不少时候优化巨大比如本题 2.2s→0.8s2.2s\to 0.8s2.2s→0.8s)
完整代码
saisa_isai排名为 iii 的后缀的编号 rkirk_irki后缀 iii 的排名
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
const int N1e6100;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
int n,m,k;
char s[N];
int rk[N1],oldrk[N1],id[N],sa[N],cnt[N],p;
void write(int x){if(x9) write(x/10);putchar(0x%10);return;
}
signed main() {
#ifndef ONLINE_JUDGE//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);
#endifscanf( %s,s1);nstrlen(s1);m122;for(int i1;in;i) cnt[rk[i]s[i]];for(int i1;im;i) cnt[i]cnt[i-1];for(int in;i1;i--) sa[cnt[rk[i]]--]i;for(int w1;;w1){p0;for(int in;in-w;i--) id[p]i;for(int i1;in;i){if(sa[i]w) id[p]sa[i]-w;}memset(cnt,0,sizeof(cnt));memcpy(oldrk,rk,sizeof(rk));for(int i1;in;i) cnt[rk[id[i]]];for(int i1;im;i) cnt[i]cnt[i-1];for(int in;i1;i--) sa[cnt[rk[id[i]]]--]id[i];p0;for(int i1;in;i){if(oldrk[sa[i]]oldrk[sa[i-1]]oldrk[sa[i]w]oldrk[sa[i-1]w]) rk[sa[i]]p;else rk[sa[i]]p;}mp;if(mn) break;//优化3}for(int i1;in;i) write(sa[i]),putchar( );return 0;
}
/**/LCP与height
定义 height(i)height(i)height(i) 表示后缀 saisa_isai 和后缀 sai−1sa_{i-1}sai−1 的最长公共前缀lcp(sai,sai−1)lcp(sa_i,sa_{i-1})lcp(sai,sai−1)。特别的lcp(1)0lcp(1)0lcp(1)0 感性理解来说把所有后缀按照字典序排序后height(i)height(i)height(i) 就是相邻两个后缀的相同部分的长度。 引理1lcp(i,j)min(lcpi,k,lcpk,j)lcp(i,j)\min (lcp_{i,k},lcp_{k,j})lcp(i,j)min(lcpi,k,lcpk,j)对于任意的 i≤k≤ji\le k\le ji≤k≤j 均成立. 证明 首先min(lcpi,k,lcpk,j)\min (lcp_{i,k},lcp_{k,j})min(lcpi,k,lcpk,j) 是 kkk 与 i,ji,ji,j 共同的公共前缀所以也必然是 i,ji,ji,j 的公共前缀lcp(i,j)≥min(lcpi,k,lcpk,j)lcp(i,j)\ge\min (lcp_{i,k},lcp_{k,j})lcp(i,j)≥min(lcpi,k,lcpk,j)。 同时由于字典序单调的性质iii 变到 kkk 变化的前缀在 kkk 变化到 jjj 时必然不可能再变回来否则 jjj 的字典序就比 kkk 小了所以有 lcp(i,j)≤min(lcpi,k,lcpk,j)lcp(i,j)\le\min (lcp_{i,k},lcp_{k,j})lcp(i,j)≤min(lcpi,k,lcpk,j)。 综上lcp(i,j)min(lcpi,k,lcpk,j)lcp(i,j)\min (lcp_{i,k},lcp_{k,j})lcp(i,j)min(lcpi,k,lcpk,j)证毕。 引理2heightrki≥heightrki−1−1height_{rk_i}\ge height_{rk_{i-1}}-1heightrki≥heightrki−1−1 证明 rki−1≤1rk_{i-1}\le1rki−1≤1 时显然成立 rki−11rk_{i-1}1rki−11 时设 rki−1−1krk_{i-1}-1krki−1−1kkkk 就是 i−1i-1i−1 按字典序排序后的前一个那么 若 i−1i-1i−1 和 kkk 的首字母不同 hi−10h_{i-1}0hi−10 显然成立 若 i−1i-1i−1 和 kkk 的首字母相同那么考虑字符串 k1k1k1由于k 去掉首字符变成 k1i-1 去掉首字母变成 i所以 k1k1k1 也一定在 iii 的前面同时 lcp(k1,i)lcp(k,i−1)−1heightrki−1−1lcp(k1,i)lcp(k,i-1)-1height_{rk{i-1}}-1lcp(k1,i)lcp(k,i−1)−1heightrki−1−1由引理1有 lcp(k1,i)min(lcp(k1,rki−1),lcp(i−1,i))lcp(k1,i)\min (lcp(k1,rk_i-1),lcp(i-1,i))lcp(k1,i)min(lcp(k1,rki−1),lcp(i−1,i))故 lcp(i−1,i)≥heightrki−1−1lcp(i-1,i)\ge height_{rk{i-1}}-1lcp(i−1,i)≥heightrki−1−1即 heightrki≥heightrki−1−1height_{rk_i}\ge height_{rk_{i-1}}-1heightrki≥heightrki−1−1 得证。 得出这个性质后线性求 heightheightheight 的代码就不难写出了
for(int i1,k0;in;i){if(k) --k;while(s[ik]s[sa[rk[i]-1]k]) k;ht[rk[i]]k;
}Thanks for reading!
