首页 > 其他分享 >Lyndon 理论学习笔记

Lyndon 理论学习笔记

时间:2024-10-30 17:02:44浏览次数:1  
标签:dots 后缀 笔记 学习 起头 kw Lyndon 引理

字符串,太深刻了 /kk

定义

下标从 1 开始。

\(+\) 是字符串拼接。

\(|s|\) 表示 \(s\) 的长度。

\(s_i\) 表示 \(s\) 的第 \(i\) 个字符。

\(s^k\) 表示 \(k\) 个 \(s\) 拼接的结果。

字符串间的大小关系用字典序比较。

Lyndon 串

字符串 \(s\) 是 Lyndon 串当且仅当 \(s\) 小于其每个非空后缀。

有的文章里的“简单串”就是 Lyndon 串。

Lyndon 分解

若字符串 \(s=w_1+\dots+w_k\),且 \(w_1\dots w_k\) 都是 Lyndon 串,且 \(w\) 字典序单调不增(\(w_i\ge w_{i+1}\)),

则 \(w_1\dots w_k\) 是 \(s\) 的 Lyndon 分解。

引理 1:\(s\) 字典序最小的后缀为 \(w_k\)。

证明:任意 \(w_i\) 都小于其每个非空后缀,所以从 \(w_i\) 起头一定比从 \(w_i\) 中间起头(也就是以 \(w_i\) 的某个非空后缀起头)优,

而 \(w_k\) 小于 \(w_i(i\ne k)\),所以从 \(w_k\) 起头一定比从 \(w_i\) 起头优,则肯定从 \(w_k\) 起头,这个后缀就是 \(w_k\)。

引理 2:Lyndon 分解唯一存在。

证明:由引理 1 可以唯一确定 \(w_k\),而 \(w_1\dots w_{k-1}\) 一定是 \(s\) 去掉 \(w_k\) 后的串的 Lyndon 分解,于是可以确定 \(w_{k-1}\),

以此类推,可以唯一确定 \(w_1\dots w_k\)。

由引理 2 可以轻松得到一个 \(O(n^2)\) 的 Lyndon 分解算法,但是这显然不是我们想要的。

Duval 算法可以 \(O(n)\) 求出 Lyndon 分解。

定义字符串 \(s\) 是近似 Lyndon 串,当且仅当 \(s=w^kw'\),其中 \(w\) 是任意 Lyndon 串,\(k\ge 1\),\(w'\) 是 \(w\) 的前缀(可以空)。

划分 \(s=s_1+s_2+s_3\),其中 \(s_1\) 的 Lyndon 分解已经得出,\(s_2\) 是一个近似 Lyndon 串,\(s_3\) 无要求,

初始 \(s_1\) 为空,\(s_2\) 是 \(s\) 的第一个字符(单字符肯定是近似 Lyndon 串),\(s_3\) 是 \(s\) 去掉第一个字符后的串,

现在需要调整划分方案,使得 \(s_1=s\),\(s_2\) 和 \(s_3\) 为空。

设 \(s_2=w^kw'\),\(x=w_{|w'|+1}\),尝试每次去掉 \(s_3\) 开头的字符 \(y\) 加到 \(s_2\) 末尾,考虑 \(x,y\) 的关系:

  • \(x=y\):\(w^kw'+x\) 仍是近似 Lyndon 串,无需调整划分方案,更新一下 \(w'\) 即可。
  • \(x<y\):\(w^kw'+y\) 是 Lyndon 串。

证明:设 \(t=w^kw'+y\)。需要证明 \(t\) 字典序最小的后缀是 \(t\) 本身。
引理 1 已经证过从 \(w\) 起头一定比从 \(w\) 中间起头优,
由 \(x<y\) 得 \(w'+y>w\),而从第 \(i(i\ne 1)\) 个 \(w\) 起头比从第一个 \(w\) 起头先走到 \(w'+y\),
则从第一个 \(w\) 起头一定比从第 \(i\) 个 \(w\) 起头优,则肯定从第一个 \(w\) 起头,这个后缀就是 \(t\) 本身。

Lyndon 串肯定也是近似 Lyndon 串,所以也无需调整划分方案,

但 \(w'+y\) 并不是 \(w\) 的前缀,所以需要更新 \(w=t\),\(w'=\varnothing\)。

  • \(x>y\):\(w^kw'+y\) 啥也不是,必须调整划分方案。把 \(k\) 个 \(w\) 划分进 \(s_1\),令 \(s_2\) 为 \(s_1\) 后第一个字符,\(s_3\) 为剩下的串即可。

标签:dots,后缀,笔记,学习,起头,kw,Lyndon,引理
From: https://www.cnblogs.com/5k-sync-closer/p/18516159

相关文章

  • 10月30日记录(《代码大全》(第二版)精读笔记)
    《代码大全》中对于“代码质量”和“设计原则”的探讨深刻而全面,给我留下了深刻的印象。在当今快速发展的软件开发环境中,理解和应用这些概念对于提升开发效率和软件质量至关重要。首先,关于代码质量,麦克康奈尔强调了代码不仅需要正确实现功能,还必须具备良好的可读性和可维护性。代......
  • [Python学习日记-58] 开发基础练习1——员工信息查询
    [Python学习日记-58]开发基础练习1——员工信息查询简介题目答案简介        该练习结合了函数和一些常用的模块开发了一个使用命令行交互的员工信息查询程序,可以巩固实践之前学习的内容。题目一、程序需求        现要求你写⼀个简单的员⼯信息增删......
  • CNN+迁移学习=中科院2区Idea!可以直接抄!
    2024深度学习发论文&模型涨点之——CNN+迁移学习CNN(卷积神经网络)是一种深度学习模型,广泛应用于图像识别、计算机视觉等领域。它通过局部连接和权值共享的机制,有效地捕捉图像中的特征,例如边缘、纹理等。迁移学习是一种机器学习技术,它允许一个预训练的模型被调整并应用于一个不......
  • 机器学习大纲总结
    一、概念1.人工智能人工智能包含机器学习,机器学习包含深度学习2.机器学习机器学习是实现人工智能的一种途径机器学习=传统机器学习+深度学习3.深度学习深度学习是由机器学习的一种方法发展而来4.发展三要素数据、算法、算力5.发展史5.1符号主义(20世纪50-7......
  • 小白江科大stm32笔记
    P5        GPIO输出·带FT的引脚可容忍5v电压·所有的GPIO都是在APB2外设总线上·每个GPIO总共有16个引脚,从0到15·32是32位单片机,寄存器有32位,但只有16个端口,所以只有低16位有端口下图为GPIO基本结构:  ·以下面GPIO电路图为例,左三为寄存器,中间为驱动器,右边为......
  • Javabase笔记分享
    JAVA1.词组proiect项目create创建src代码存放源文件new新建package包(分类存放)命名:com.公司.用途class类(写代码)Test测试System.out.println系统.输出.打印(Syso再用alt+回车键)2.数据类型整数(4个)byte->short->int->long其中int和long最为常用小数(2个)f......
  • 算法网关视频分析网关算法定制:适合视频分析的深度学习架构及视频分析原理和应用
    随着信息技术的突飞猛进,视频监控技术已经从模拟监控时代跨入了高清、智能化的新纪元。在这场技术革新中,算法定制视频分析网关扮演着至关重要的角色,它作为连接前端摄像头与后端管理平台的桥梁,其作用日益凸显,不可或缺。一、适合视频分析的深度学习架构深度学习在视频监控系统中的......
  • HTML笔记(2)
    该笔记为观看acwing(acwing.com)后编写,其中部分内容转自acwing,如有侵权请联系我HTML基础标签文本标签虽然很多,但大部分可看成是预定好样式的<div>和<span>div标签<div>元素(或HTML文档分区元素)是一个通用型的流内容容器,在不使用CSS的情况下,其对内容或布局没有任......
  • 代码大全2阅读笔记
    代码大全2阅读笔记《代码大全2》还是一本关于软件开发的全面指南,内容包括了代码质量、设计原则、构建发布、调试性能优化和实际案例经验。在这本书中,调试和性能优化这两个领域的重要性尤为突出,而作者通过实际案例和经验分享,向读者展示了如何将理论知识应用于实际工作中,并解决实际......
  • TS学习笔记(四)
    1.类型缩小(联合类型)对变量进行类型缩小,除了使用as断言外,还可以使用ifelse(switch也行)。如下functionprintId(id:number|string){if(typeofid==='string'){console.log(id.toUpperCase());}else{console.log(id);}}类型缩小是TS处理联合......