后缀排序模板

2021-06-10 06:05

阅读：413

标签：排名 http for div 证明 names while using display

题链

sa

\(sa[i]\)表示排名\(i\)的开头
\(rk[i]，x[i]\)表示\(i\)后缀所在的排名
\(y[i]\)表示的第二段排名为\(i\)的开头
\(c[i]\)为桶
倍增

#include
using namespace std;

const int N=1e5+5;
int n,m,x[Nk) y[++num]=sa[i]-k;
		}
		for(int i=1;i

LCP,height

\(LCP(i,j)\)表示\(sa[i...j]\)的最长公共前缀长度
\(height[i]\) 表示\(LCP(i,i-1)\)
\(h[i]\)表示\(height[rk[i]]\)

性质1:

\[ LCP(i,k)=min(LCP(i,j),LCP(j,k)),i\leq j\leq k \]

性质2：

\[ LCP(i,k)=min_{i

性质3：

\[ h[i]>=h[i-1]-1,rk[i]>1 \]

用\(feel\)法可证明

	for(int i=1;i

后缀排序模板

标签：排名 http for div 证明 names while using display

原文地址：https://www.cnblogs.com/wsfwsf/p/14462937.html

上一篇：R语言barplot ，掌握本篇的内容，基本的条形图都可以画了

下一篇：如何掌握 C 语言的一大利器——指针？

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：后缀排序模板
文章链接：http://soscw.com/index.php/essay/93024.html

评论

亲，登录后才可以留言！

关于我们 | 版权声明 | 常见问题 | 素材投稿 | 联系我们 | 网站地图 |

搜素材网素材除本站原创外均由用户分享，若发现权利被侵害，请联系及时联系我们，我们会在第一时间进行处理。

特别说明：本站所有资源除本站原创外仅供学习与参考，请勿用于商业用途,如有侵犯您的版权请联系客服服务QQ：

点击这里给我发消息

Copyright © 2024 soscw.com 搜素材网素材网版权所有蜀ICP备18015633号-1