[学习笔记]后缀相关算法
2022/2/25 17:26:19
本文主要是介绍[学习笔记]后缀相关算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
SA
SA实际上求出两个数组\(sa,rk\)。
\(sa_i\)表示将所有后缀排序后排名第\(i\)小的后缀的编号,\(rk_i\)表示后缀\(i\)的排名。
满足其性质\(sa_{rk_i} = rk_{sa_i} = i\)
这里仅给出一个\(O(nlog^2n)\)的做法。
其他做法参见\(oiwiki\)。
点击查看代码
bool cmp(int i,int j){ if(rk[i]!=rk[j]){ return rk[i]<rk[j]; }else{ int ri,rj; ri=i+k<n?rk[i+k]:-1; rj=j+k<n?rk[j+k]:-1; return ri<rj; } } void calc(){ for(int i=0;i<n;i++){ rk[i]=s[i]; sa[i]=i; } for(k=1;k<n;k*=2){ sort(sa,sa+n,cmp); tmp[sa[0]]=0; for(int i=0;i<n-1;i++){ tmp[sa[i+1]]=tmp[sa[i]]+cmp(sa[i],sa[i+1]); } for(int i=0;i<n;i++){ rk[i]=tmp[i]; } } }
很多情况下我们都要求出辅助数组\(height\)数组。
\(height_i = lcp(sa_i,sa_{i - 1})\)
其有引理\(height_{rk_{i - 1}} + 1 \leq height_{rk_{i}}\)
所以根据该引理,维护一个指针即可\(O(n)\)求出其。
点击查看代码
for (i = 1, k = 0; i <= n; ++i) { if (rk[i] == 0) continue; if (k) --k; while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k; height[rk[i]] = k; }
其应用大概有:
两个子串最长公共前缀:
\(lcp(sa_i,sa_j) = \min{heaight_{i + 1...j}}\)
不同子串数目:
\(\frac{n(n+1))}{2} - \sum_{i = 2}^n height_i\)
连续的相同子串([NOI2016] 优秀的拆分):
考虑枚举长度然后设置关键点。
若存在\(AA\),则\(AA\)一定跨越两个关键点,枚举两关键点,其一定有\([1,x][1,y]\)的后缀最长公共子串加\([x,n][y,n]\)的前缀最长公共子串大于枚举长度。
配合图食用。
搭配其他数据结构
这篇关于[学习笔记]后缀相关算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性
- 2024-05-29哪些无用敏捷指标正在破坏敏捷转型?
- 2024-05-29鸿蒙原生应用再新丁!新华社 入局鸿蒙
- 2024-05-29设计模式 之 迭代器模式(Iterator)