当前位置: 首页 > 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…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

Spring AI与Spring Modulith核心技术解析

Spring AI核心架构解析 Spring AI&#xff08;https://spring.io/projects/spring-ai&#xff09;作为Spring生态中的AI集成框架&#xff0c;其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似&#xff0c;但特别为多语…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...