后缀树与后缀数组简介及代码模板 ← AcWing 2715

【题目来源】
https://www.acwing.com/problem/content/2717/

【题目描述】
给定一个长度为 n 的字符串,只包含大小写英文字母和数字。
将字符串中的 n 个字符的位置编号按顺序设为 1∼n。
并将该字符串的 n 个非空后缀用其起始字符在字符串中的位置编号表示。
现在要对这 n 个非空后缀进行字典序排序,并给定两个数组 SA 和 Height。
排序完成后,用 SA[i] 来记录排名为 i 的非空后缀的编号,用 Height[i] 来记录排名为 i 的非空后缀与排名为 i−1 的非空后缀的最长公共前缀的长度(1≤i≤n)。
特别的,规定 Height[1]=0。
请你求出这两个数组。

【输入格式】
共一行,包含一个长度为 n 的仅包含大小写英文字母或数字的字符串。

【输出格式】
第一行包含 n 个整数,表示 SA 数组。
第二行包含 n 个整数,表示 Height 数组。

【数据范围】
1≤n≤10^6

【输入样例】
abababab

【输出样例】
7 5 3 1 8 6 4 2
0 2 4 6 0 1 3 5

【后缀树及后缀数组简介】

后缀(Suffix):字符串的后缀是指从字符串某个位置开始到末尾的所有子串。例如,字符串 s[]="abcdefg" 的后缀为 s[0]="abcdefg"、s[1]="bcdefg"、s[2]="cdefg"、s[3]="defg"、s[4]="efg"、s[5]="fg"、s[6]="g" 等。

后缀树(Suffix Tree):将字符串的所有后缀子串用字典树的方法建立的树。换句话说,后缀树的本质是把一个长度为 n 的字符串拆成 n 个后缀子串,然后按字典序来构造。后缀树的根结点为空,后缀树中每个后缀子串的末尾用符号 $ 表示
例如,字符串 s[]="banana" 的后缀为 s[0]="banana"、s[1]="anana"、s[2]="nana"、s[3]="ana"、s[4]="na"、s[5]="a",其对应的后缀树如图所示。
 



● 长度为 n 的字符串,其 n 个后缀子串的长度分别为 n,n-1,n-2,……,2,1,总长度为 n(n+1)/2。可见,后缀树的空间复杂度比较差,为 O(n^2)。故引入后缀数组 sa (Suffix Array)来代替后缀树。

后缀数组 sa(Suffix Array):后缀数组 sa 的值就是将字符串的所有后缀子串按字典序排序后对应的原始下标。
例如,字符串 s[]="banana" 的后缀为 s[0]="banana"、s[1]="anana"、s[2]="nana"、s[3]="ana"、s[4]="na"、s[5]="a",其对应的后缀数组 sa[]={5,3,1,0,4,2}。求解过程如下图所示。

后缀数组元素 sa[i],是原字符串中从第 i 个位置开始的后缀子串(下标从 0 开始)。例如,在上图所示后缀数组 sa 中,sa[1]=3,表示排名 1 的子串,是原字符串 banana 中从第 1 个位置开始的后缀子串,即 ana。

● 在后缀数组的代码实现中,有 3 个关键的数组:后缀数组 sa[]、名次数组 rk[]、高度数组 height[]。其中,sa[] 与 rk[] 是一一对应关系,互为逆运算。
由 sa[] 数组推出 rk[] 数组在实战中常用
由 rk[] 数组推出 sa[] 数组的代码如下所示:

for(int i=0; i<n; i++) sa[rk[i]]=i;

由 sa[] 数组推出 rk[] 数组的代码如下所示:

for(int i=0; i<n; i++) rk[sa[i]]=i;

例如,由上文已知,字符串 s[]="banana" 的后缀为 s[0]="banana"、s[1]="anana"、s[2]="nana"、s[3]="ana"、s[4]="na"、s[5]="a",其对应的后缀数组 sa[]={5,3,1,0,4,2}。
据 sa[] 数组推出 rk[] 数组的代码
rk[sa[i]]=i 可得:
rk[sa[
0]]=rk[5]=0
rk[sa[1]]=rk[3]=1
rk[sa[2]]=rk[1]=2
rk[sa[3]]=rk[0]=3
rk[sa[4]]=rk[4]=4
rk[sa[5]]=rk[2]=5
由上显见,rk[i] 的值为原字符串的第 i 个后缀子串,在原字符串所有后缀子串按字典序排序后,其所处的位序

【算法代码】

#include <bits/stdc++.h>
using namespace std;const int maxn=1e6+5;//sa[i] 表示字典序排名为 i 的后缀处于原字符串所有后缀的位序
//rk[i] 表示原字符串第 i 个后缀的字典序排名
//height[i] 表示排名第 i 的后缀和排名第 i - 1 的后缀的最长公共前缀
//fi[i] 表示第 i 个后缀的第一关键字
//se[i] 表示第 i 个后缀的第二关键字
//c[i] 表示关键字为 i 的数的个数
int sa[maxn],rk[maxn];
int height[maxn];
int fi[maxn],se[maxn],c[maxn];char s[maxn];
int n,m;void get_sa() {for(int i=1; i<=n; i++) c[fi[i]=s[i]]++;for(int i=2; i<=m; i++) c[i]+=c[i-1]; //prefix sumfor(int i=n; i>=1; i--) sa[c[fi[i]]--]=i;for(int k=1; k<=n; k<<=1) {//Radix Sort based on 2nd keyint num=0;for(int i=n-k+1; i<=n; i++) se[++num]=i;for(int i=1; i<=n; i++)if(sa[i]>k) se[++num]=sa[i]-k;//Radix Sort based on 1st keyfor(int i=1; i<=m; i++) c[i]=0;for(int i=1; i<=n; i++) c[fi[i]]++;for(int i=2; i<=m; i++) c[i]+=c[i-1];for(int i=n; i>=1; i--) sa[c[fi[se[i]]]--]=se[i], se[i]=0;//Discretize all sorted suffixes according to the first 2K charactersswap(fi,se);fi[sa[1]]=1, num=1;for(int i=2; i<=n; i++) {if(se[sa[i]]==se[sa[i-1]] && se[sa[i]+k]==se[sa[i-1]+k]) fi[sa[i]]=num;else fi[sa[i]]=++num;}if(num==n) break;m=num;}
}void get_height() {for(int i=1; i<=n; i++) rk[sa[i]]=i;for(int i=1, k=0; i<=n; i++) {if(rk[i]==1) continue;if(k) k--;int j=sa[rk[i]-1];while(i+k<=n && j+k<=n && s[i+k]==s[j+k]) k++;height[rk[i]]=k;}
}int main() {scanf("%s", s+1);n=strlen(s+1);m=122; //ASCII of 'z' is 122get_sa();get_height();for(int i=1; i<=n; i++) printf("%d ",sa[i]);printf("\n");for(int i=1; i<=n; i++) printf("%d ", height[i]);return 0;
}/*
in:
ababababout:
7 5 3 1 8 6 4 2
0 2 4 6 0 1 3 5
*/




【参考文献】
https://www.acwing.com/solution/content/163123/
https://www.acwing.com/solution/content/58924/

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/324386.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

保姆级零基础微调大模型(LLaMa-Factory,多卡版)

此处非常感谢https://github.com/hiyouga/LLaMA-Factory这个项目。 看到网上的教程很多都是教如何用webui来微调的,这里出一期命令行多卡微调教程~ 1. 模型准备 模型下载比较方便的方法: 1. modelscope社区(首选,速度很高,并且很多需要申请的模型都有)注意要选择代码…

「TypeScript」TypeScript入门练手题

前言 TypeScript 越来越火&#xff0c;现在很多前端团队都使用它&#xff0c;因此咱们前端码农要想胜任以后的前端工作&#xff0c;就要更加熟悉它。 入门练手题 interface A {x: number;y: number; }type T Partial<A>;const a: T { x: 0, y: 0 }; const b: T { …

Web3 Tools - Base58

Base58编码 Base58编码是一种用于表示数字的非常见的编码方法。它通常用于加密货币领域&#xff0c;例如比特币和其他加密货币的地址表示。 什么是Base58编码&#xff1f; Base58编码是一种将数字转换为人类可读形式的编码方法。与常见的Base64编码不同&#xff0c;Base58编码…

JVM调参实践总结

JVM调优–理论篇从理论层面介绍了如何对JVM调优。这里再写一篇WIKI&#xff0c;尝试记录下JVM参数使用的最佳实践&#xff0c;注意&#xff0c;这里重点介绍HotSpot VM的调参&#xff0c;其他JVM的调参可以类比&#xff0c;但不可照搬。 Java版本选择 基于Java开发应用时&…

【问题分析】锁屏界面调起google语音助手后壁纸不可见【Android 14】

1 问题描述 为系统和锁屏分别设置两张不同的壁纸&#xff0c;然后在锁屏界面长按Power调起google语音助手后&#xff0c;有时候会出现壁纸不可见的情况&#xff0c;如以下截图所示&#xff1a; 有的时候又是正常的&#xff0c;但显示的也是系统壁纸&#xff0c;并非是锁屏壁纸…

Map按value降序并统计

package com.ldj.cloud.user.demo;import java.util.*;/*** User: ldj* Date: 2024/5/11* Time: 10:03* Description: map按value降序*/ public class Tr {public static void main(String[] args) {ArrayList<String> list new ArrayList<>();list.add("a&q…

纯血鸿蒙APP实战开发——阅读翻页方式案例

介绍 本示例展示手机阅读时左右翻页&#xff0c;上下翻页&#xff0c;覆盖翻页的功能。 效果图预览 使用说明 进入模块即是左右翻页模式。点击屏幕中间区域弹出上下菜单。点击设置按钮&#xff0c;弹出翻页方式切换按钮&#xff0c;点击可切换翻页方式。左右翻页方式可点击翻…

【前端】JavaScript的WebAPI | DOM | 获取元素 | 事件 | 操作元素 | 操作节点

文章目录 [toc] JavaScript的WebAPI一、DOM1.DOM树2.获取元素1.querySelector2.querySelectorAll 3.事件事件三要素点击事件键盘事件 4.操作元素获取/修改元素内容获取/修改元素属性获取/修改表单属性获取/修改样式属性行内样式操作类名样式操作 5.操作节点新增节点删除节点 Ja…

EasyRecovery数据恢复软件2024最新免费无需激活版下载

EasyRecovery数据恢复软件是一款功能强大、操作简便的数据恢复工具&#xff0c;旨在帮助用户解决各种数据丢失问题。无论是由于误删除、格式化、磁盘损坏还是其他原因导致的数据丢失&#xff0c;EasyRecovery都能提供有效的恢复方案。以下是对EasyRecovery软件功能的详细介绍。…

XWiki 服务没有正确部署在tomcat中,如何尝试手动重新部署?

1. 停止 Tomcat 服务 首先&#xff0c;您需要停止正在运行的 Tomcat 服务器&#xff0c;以确保在操作文件时不会发生冲突或数据损坏&#xff1a; sudo systemctl stop tomcat2. 清空 webapps 下的 xwiki 目录和 work 目录中相关的缓存 删除 webapps 下的 xwiki 目录和 work …

IP报文在设备间传递的封装过程

IP报文传递过程 1、PC1访问PC2报文传递过程1.1、PC1准备数据请求报文封装1.2、PC1准备ARP请求报文1.3、PC2准备ARP响应报文1.4、PC1完成数据请求报文封装 2、PC1访问PC3报文传递过程2.1、PC1准备数据请求报文封装2.2、PC1准备获取网关MAC地址的ARP请求报文2.3、网关准备ARP响应…

Github2024-05-10开日报 Top10

根据Github Trendings的统计&#xff0c;今日(2024-05-10统计)共有10个项目上榜。根据开发语言中项目的数量&#xff0c;汇总情况如下&#xff1a; 开发语言项目数量Python项目4TypeScript项目4JavaScript项目1Lua项目1C项目1Rust项目1Dart项目1 RustDesk: 用Rust编写的开源远…

【Linux】进程间通信之共享内存

&#x1f916;个人主页&#xff1a;晚风相伴-CSDN博客 &#x1f496;如果觉得内容对你有帮助的话&#xff0c;还请给博主一键三连&#xff08;点赞&#x1f49c;、收藏&#x1f9e1;、关注&#x1f49a;&#xff09;吧 &#x1f64f;如果内容有误的话&#xff0c;还望指出&…

【Linux系统编程】第十六弹---冯诺依曼体系结构与操作系统

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】【C详解】【Linux系统编程】 目录 1、冯诺依曼体系结构 2、操作系统原理 2.1、什么是操作系统&#xff1f; 2.2、用图解释操作系统 2.3、理解操作系统 总结 …

QT的TcpServer

Server服务器端 QT版本5.6.1 界面设计 工程文件&#xff1a; 添加 network 模块 头文件引入TcpServer类和TcpSocket&#xff1a;QTcpServer和QTcpSocket #include <QTcpServer> #include <QTcpSocket>创建server对象并实例化&#xff1a; /*h文件中*/QTcpServer…

NAND Flash 与 NOR Flash间的区别

非易失性存储器是一种即使未通电也能保持其内容的存储器。非易失性存储器可以有不同的形式: ROM – 只读存储器&#xff0c;数据写入一次&#xff0c;允许多次读取访问。 PROM – 可编程只读存储器&#xff0c;数据写入一次&#xff08;不是在制造过程中&#xff0c;而是以后的…

【论文速读】| LLM4FUZZ:利用大语言模型指导智能合约的模糊测试

本次分享论文&#xff1a;LLM4FUZZ: Guided Fuzzing of Smart Contracts with Large Language Models 基本信息 原文作者&#xff1a;Chaofan Shou, Jing Liu, Doudou Lu, Koushik Sen 作者单位&#xff1a;加州大学伯克利分校&#xff0c;加州大学欧文分校&#xff0c;Fuzz…

15 华三华为链路聚合综述

1 链路聚合简介 以太网链路聚合通过将多条以太网物理链路捆绑在一起形成一条以太网逻辑链路&#xff0c;实现增加链路带宽的目的&#xff0c;同时这些捆绑在一起的链路通过相互动态备份&#xff0c;可以有效地提高链路的可靠性。 2 成员端口的状态 聚合组内的成员端口具有以下…

2024年,Web开发新趋势!

随着我们迈入新的一年&#xff0c;现在正是审视2024年网页开发领域开始流行哪些趋势的绝佳时机。回顾2023年的一系列更新&#xff0c;以下是来年一些热门话题的概览。 自主托管有回归的趋势 近些年&#xff0c;自主托管一直是网页开发者和公司托管其应用程序的默认方式。开发…

蓝桥杯13届JAVA A组 国赛

​​​​​​​ package 蓝桥杯国赛; // 贪心选个数最少的进行摆 // 2:1 ,3:1, 4:1,5 : 3,6:3,7:1 // 选 1&#xff0c;7&#xff0c;4&#xff0c;2&#xff0c;3&#xff0c;5&#xff0c;9 // 然后都选满10个 public class 火彩棒数字 {public static void main(String[] a…