当前位置: 首页 > news >正文

[acm算法学习] 后缀数组SA

学习自B站up主 kouylan 

定义

后缀是包含最后个字母的子串

把字符串 str 的所有后缀按字典排序,sa[i]表示排名为 i 的后缀的开头下标

如何求解SA

倍增的方法

先把每个位置开始的长度为1的子串排序,在此基础上再把长度为2的子串排序(长度为2的子串就 是前面算过的长度为1的子串再加上后面的一位,第 i 位的和 i+1 ),再把长度为4,8,16,32...(两个两个拼)直到串的末尾,也就是排到了后缀。

如何从2^(k-1) 到 2^k

  • 记 rk[i] 表示当前长度下,i 开始的子串的排名
  • 前 2^(k-1) 和后  2^(k-1) 拼成了 2^k
  • 确定  2^k 的排名时,先比较前 2^(k-1)的rk,如果更小,那么整个也更小,不用比后面了;如果前 2^(k-1)相等,则去比较后  2^(k-1) 的rk

up主给的这个图很形象

原串中下标位置为1的a,会去和原串中下标为2的b拼一起,a(1)和a(6)的rk相同,所以比较后面部分,b(2) 比 c(7) 的 rk 要先,所以最后长度为2的 rk 里ab 比 ac 要前。由于c(7)是最后一位了,所以它的下一位是个空串,我们定义空串的rk是-1,这样,因为没有比空串还小的了,设为-1可以达到效果。

求解程序

sa 是根据 rk 来的,根据排序好的 sa 来更新 rk2 (使用临时变量 rk2),因为更新的过程中要用到上一次的 rk ,初始的rk是字典序。

用sort在当前 k 下把 sa 数组排好顺序,然后再遍历一遍数组sa把对应位置的字母排名依次排好。最后更新一遍rk。

重载的排序函数,是根据先比前一半,后比后一半。

时间复杂度 n*log(n)*log(n)

相关文章:

[acm算法学习] 后缀数组SA

学习自B站up主 kouylan 定义 后缀是包含最后个字母的子串 把字符串 str 的所有后缀按字典排序,sa[i]表示排名为 i 的后缀的开头下标 如何求解SA 倍增的方法 先把每个位置开始的长度为1的子串排序,在此基础上再把长度为2的子串排序(长度…...

DNS解析和它的三个实验

一、DNS介绍 DNS:domain name server 7层协议 名称解析协议 tcp /53 主从之间的同步 udp/53 名字解析 DNS作用:将域名转换成IP地址的协议 1.1DNS的两种实现方式 1.通过hosts文件(优先级最高) 分散的管理 linux /etc/hos…...

[redis] redis的安装,配置与简单操作

一、缓存的相关知识 1.1 缓存的概念 缓存是为了调节速度不一致的两个或多个不同的物质的速度,在中间对速度较慢的一方起到加速作用,比如CPU的一级、二级缓存是保存了CPU最近经常访问的数据,内存是保存CPU经常访问硬盘的数据,而且…...

C++ STL set容器

和 map、multimap 容器不同&#xff0c;使用 set 容器存储的各个键值对&#xff0c;要求键 key 和值 value 必须相等。 举个例子&#xff0c;如下有 2 组键值对数据&#xff1a; {<a, 1>, <b, 2>, <c, 3>} {<a, a>, <b, b>, <c, c>} 显然&…...

专业课148,总分410+电子科技大学858信号与系统考研经验电子信息与通信

今年专业课148分&#xff0c;总分410顺利被电子科技大学录取&#xff0c;回望这一年复习还有很多不足&#xff0c;总结一下自己的复习经历&#xff0c;希望对大家复习有所帮助。 数学&#xff1a;&#xff08;多动手&#xff0c;多计算&#xff0c;多总结&#xff0c;打好基础…...

密码学:一文读懂非对称加密算法 DH、RSA

文章目录 前言非对称加密算法的由来非对称加密算法的家谱1.基于因子分解难题2.基于离散对数难题 密钥交换算法-DH密钥交换算法-DH的通信模型初始化DH算法密钥对甲方构建DH算法本地密钥乙方构建DH算法本地密钥DH算法加密消息传递 典型非对称加密算法-RSARSA的通信模型RSA特有的的…...

ZooKeeper 实战(二) 命令行操作篇

文章目录 ZooKeeper 实战(二) 命令行操作篇1. 服务端命令1.1. 服务启动1.2. 查看服务1.3. 重启服务1.4. 停止服务 2. 客户端命令2.1. 启动客户端2.2. 查看节点信息查看根节点详情 ls -s /添加一个watch监视器 ls -w /列举出节点的级联节点 ls -R / 2.3. 查看节点状态2.4. 创建节…...

关于在前台应用路由调用子应用

需求 在实际写项目的过程中&#xff0c;关于一些前台的官网首页&#xff0c;会需要在一写特定的路由侠调用子应用的需求&#xff0c;在编写的过程中在公用的方法中&#xff0c;来进行处理&#xff0c;处理思想如下&#xff0c;在特定的.vue文件中&#xff0c; 后端 通过后端…...

Spring学习 Spring事务控制

7.1.事务介绍 7.1.1.什么是事务&#xff1f; 当你需要一次执行多条SQL语句时&#xff0c;可以使用事务。通俗一点说&#xff0c;如果这几条SQL语句全部执行成功&#xff0c;则才对数据库进行一次更新&#xff0c;如果有一条SQL语句执行失败&#xff0c;则这几条SQL语句全部不…...

c++一些使用频率较高的库函数

目录 memset&#xff08;&#xff09; memset&#xff08;&#xff09;接受三个参数&#xff1a; 注意 swap&#xff08;&#xff09; reverse&#xff08;&#xff09; reverse函数接收两个参数&#xff1a; reverse&#xff08;&#xff09;反转整形向量元素顺序示例 …...

【从零开始学技术】Fiddler 抓取 https 请求大全

1.Fiddler代理浏览器设置 注意浏览器代理区别 Chrome/IE浏览器使用的都是系统代理设置 在chrome浏览器的设置中搜索代理&#xff0c;可以看到 打开IE浏览器&#xff0c;选择设置->Internet选项 Firefox浏览器使用的是单独的一套代理系统 在Firefox的代理设置中&#xff0c;我…...

第二百六十四回

文章目录 概念介绍使用方法示例代码 我们在上一章回中介绍了SliverPadding组件相关的内容&#xff0c;本章回中将介绍Sliver综合示例.闲话休提&#xff0c;让我们一起Talk Flutter吧。 概念介绍 我们在前面的章回中介绍了各种Sliver相关的组件&#xff1a;SliverList,SliverGr…...

用Kimi chat识别并整理图片里面的文字

Kimi chat是有OCR功能的&#xff0c;可以识别图片中的文字。 下面这张图片是一本书的注释&#xff0c;里面提到有不少图书&#xff0c;利用Kimi chat就可以轻松完成提取其中图书书名的任务。 先拿一张图片来做实验。Kimichat的回复&#xff1a; 在您提供的文件内容中&#xf…...

驾驭未来:从传统运维到智能化运维的转型之路

随着科技的飞速发展&#xff0c;企业的业务需求也在不断变化。为了满足这些需求&#xff0c;企业的IT架构逐渐向云原生、容器化和微服务化演进。作为支撑企业业务发展的运维人员&#xff0c;我们需要紧跟时代步伐&#xff0c;不断提升自己的技能和认知水平。 在2023年全球运维大…...

LabVIEW在旋转机械故障诊断中的随机共振增强应用

在现代工业自动化领域&#xff0c;准确的故障诊断对于保障机械设备的稳定运行至关重要。传统的故障检测方法往往因噪声干扰而难以捕捉到微弱的故障信号。随着LabVIEW在数据处理和系统集成方面的优势日益凸显&#xff0c;其在旋转机械故障诊断中的应用开始发挥重要作用&#xff…...

尚硅谷大数据技术-数据湖Hudi视频教程-笔记02【核心概念(基本概念、数据写、数据读)】

大数据新风口&#xff1a;Hudi数据湖&#xff08;尚硅谷&Apache Hudi联合出品&#xff09; B站直达&#xff1a;https://www.bilibili.com/video/BV1ue4y1i7na 尚硅谷数据湖Hudi视频教程百度网盘&#xff1a;https://pan.baidu.com/s/1NkPku5Pp-l0gfgoo63hR-Q?pwdyyds阿里…...

鸿蒙(HarmonyOS)应用开发指南

1. 概述 1.1 简介 鸿蒙&#xff08;即 HarmonyOS &#xff0c;开发代号 Ark&#xff0c;正式名称为华为终端鸿蒙智能设备操作系统软件&#xff09;是华为公司自 2012 年以来开发的一款可支持鸿蒙原生应用和兼容 AOSP 应用的分布式操作系统。该系统利用“分布式”技术将手机、电…...

Android 13 辅助屏导航栏不显示问题

问题 在Android 13 上开启辅助屏幕。但是发现辅助屏systemui 导航按 icon没有显示&#xff0c;但是点击对应的区域有作用 分析 可以用 anroid device monitor 工具分析视图 解决 public NavigationBarView(Context context, AttributeSet attrs) {super(context, attrs);…...

【QT】标准对话框

目录 1 概述 2 QFileDialog对话框 1.选择打开一个文件 2.选择打开多个文件 3&#xff0e;选择已有目录 4&#xff0e;选择保存文件名 3 QColorDialog对话框 4 QFontDialog对话框 5 QInputDialog标准输入对话框 1.输入文字 2&#xff0e;输入整数 3&#xff0e;输入…...

微信小程序跳转方式及问题

一、五种跳转方式 1.wx.navigateTo() 保留当前页面&#xff0c;跳转到应用内的某个页面。但是不能跳到 tabbar 页面 通常推荐使用 wx.navigateTo进行跳转&#xff0c;以便返回原页面&#xff0c;以提高加载速度 wx.navigateTo({url: })2.wx.redirectTo() 关闭当前页面&#x…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

PHP和Node.js哪个更爽?

先说结论&#xff0c;rust完胜。 php&#xff1a;laravel&#xff0c;swoole&#xff0c;webman&#xff0c;最开始在苏宁的时候写了几年php&#xff0c;当时觉得php真的是世界上最好的语言&#xff0c;因为当初活在舒适圈里&#xff0c;不愿意跳出来&#xff0c;就好比当初活在…...

iPhone密码忘记了办?iPhoneUnlocker,iPhone解锁工具Aiseesoft iPhone Unlocker 高级注册版​分享

平时用 iPhone 的时候&#xff0c;难免会碰到解锁的麻烦事。比如密码忘了、人脸识别 / 指纹识别突然不灵&#xff0c;或者买了二手 iPhone 却被原来的 iCloud 账号锁住&#xff0c;这时候就需要靠谱的解锁工具来帮忙了。Aiseesoft iPhone Unlocker 就是专门解决这些问题的软件&…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

【AI学习】三、AI算法中的向量

在人工智能&#xff08;AI&#xff09;算法中&#xff0c;向量&#xff08;Vector&#xff09;是一种将现实世界中的数据&#xff08;如图像、文本、音频等&#xff09;转化为计算机可处理的数值型特征表示的工具。它是连接人类认知&#xff08;如语义、视觉特征&#xff09;与…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

Redis的发布订阅模式与专业的 MQ(如 Kafka, RabbitMQ)相比,优缺点是什么?适用于哪些场景?

Redis 的发布订阅&#xff08;Pub/Sub&#xff09;模式与专业的 MQ&#xff08;Message Queue&#xff09;如 Kafka、RabbitMQ 进行比较&#xff0c;核心的权衡点在于&#xff1a;简单与速度 vs. 可靠与功能。 下面我们详细展开对比。 Redis Pub/Sub 的核心特点 它是一个发后…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...