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

利用最小二乘法找圆心和半径

#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

10-Oracle 23 ai Vector Search 概述和参数

一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI&#xff0c;使用客户端或是内部自己搭建集成大模型的终端&#xff0c;加速与大型语言模型&#xff08;LLM&#xff09;的结合&#xff0c;同时使用检索增强生成&#xff08;Retrieval Augmented Generation &#…...

SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题

分区配置 (ptab.json) img 属性介绍&#xff1a; img 属性指定分区存放的 image 名称&#xff0c;指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件&#xff0c;则以 proj_name:binary_name 格式指定文件名&#xff0c; proj_name 为工程 名&…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

【深度学习新浪潮】什么是credit assignment problem?

Credit Assignment Problem(信用分配问题) 是机器学习,尤其是强化学习(RL)中的核心挑战之一,指的是如何将最终的奖励或惩罚准确地分配给导致该结果的各个中间动作或决策。在序列决策任务中,智能体执行一系列动作后获得一个最终奖励,但每个动作对最终结果的贡献程度往往…...

java高级——高阶函数、如何定义一个函数式接口类似stream流的filter

java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用&#xff08;Math::max&#xff09; 2 函数接口…...