【学习笔记】字符串算法汇总(待更新)_weixin_38166905的博客-程序员宅基地

【学习笔记】字符串算法汇总

【大前言】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


一.【字符串哈希(Hash)】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


二.【最小表示法】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


三.【Kmp】

看毛片。

\(To\) \(be\) \(continued...\)


\[ QAQ \]


四.【扩展Kmp(ExKmp)】

儿想看毛片。

\(To\) \(be\) \(continued...\)


\[ QAQ \]


五.【马拉车(Manacher)】

1.【前言】

马拉车用于求解连续回文子串问题,效率极高。

其核心思想与 \(kmp\) 类似:继承。 ——引自 \(yyx\) 学姐


2.【算法原理】

对于任意一个回文串 \(a\),设其中点为 \(mid\)(为方便描述,偶数串则在正中央加一个位置),那么根据定义,有:

\(a[mid-1]==a[mid+1]\)
\(a[mid-2]==a[mid+2]\)
\(...\)

可知:
如果 \(a[mid-x]\) 可以形成半径为 \(r\) 的回文串,且不越过以 \(mid\) 为中心的回文串,那么 \(a[mid+x]\) 也可以形成半径为 \(r\) 的回文串。

以奇回文串为例,用 \(r[i]\) 表示以 \(i\) 为中点的最大回文串长度。
如果我们已知 \(r[mid],r[j](j \in [mid-r[mid]+1,mid-1])\),那么可以分两种情况推出其关于 \(mid\) 的对称点 \(i\) \((\frac {i+j}{2}=mid)\) 的半径:

\(R=mid+r[mid]-1\)
\((1).\) \(i+r[j]-1<=R,\) \(r[i]=r[j]\)

\((2).\) \(i+r[j]-1>R,\) \(r[i]=R-i+1\)

\(r[i]=min(r[j],R-i+1)\)

如上所述,实现了从前面信息到后面信息的继承

继承之后还需要判断以 \(i\) 为中心能否继续扩张,这时候可以直接暴力枚举扩大半径


3.【算法实现】

实时维护一个已知覆盖范围最靠右的回文串信息,记录其中点 \(mid\) 和右端点 \(R\)

\(1,n\) 枚举 \(i\)
\(i<=R\) 则可以用 \(i\) 的对称点 \(mid*2-i\) 得到 \(r[i]\)
\(i>R\)(即 \(R=i-1\) 的情况,因为 \(R\) 永远大于等于 \(i-1\)),初始化 \(r[i]=1\),然后暴力扩大求出最大 \(r[i]\)

如果以 \(i\) 为中点可以得到更靠右的回文串,更新 \(mid\)\(R\)

但偶数串不太好处理,所以在原字符串中的所有空隙中插入一个不可能出现的字符,例如 \('*',\) \('|'\) 等等,最前面和最后面也要插。
此时,奇数串还是奇数串偶数串则变成了奇数串,可以统一按照奇数串处理啦。

注意:统计答案时应取真实的回文串长度。
(具体可以自己画个图分类讨论一下,会发现无论奇偶,无论是否为原字符串中的字符,\(r[i]-1\) 始终等于以 \(i\) 为中点的实际最大回文串长度。)

【Code】

题目:\(Palindrome\) \([Poj3974]\)

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<string>
#define Re register int
using namespace std;
const int N=1e6+5;
int n,R,mid,ans,OOO,r[N<<1];char op[N],a[N<<1];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
int main(){
    while(cin>>op){
        if(op[0]=='E'&&op[1]=='N'&&op[2]=='D')break;//没用string就只能这样一位一位地判断了
        a[0]='$',a[n=1]='*',R=0,mid=0,ans=0;
        for(Re i=0;op[i];++i)a[++n]=op[i],r[n]=0,a[++n]='*',r[n]=0;//玄学填空法
        for(Re i=1;i<=n;++i){
            r[i]=i<=R?min(R-i+1,r[(mid<<1)-i]):1;//继承前辈的信息
            while(a[i-r[i]]==a[i+r[i]])++r[i];//暴力扩张领域
            if(i+r[i]-1>R)R=i+r[mid=i]-1;
            ans=max(ans,r[i]-1);//取实际回文长度
        }
        printf("Case %d: %d\n",++OOO,ans);
    }
}

4.【时间复杂度】

似乎看起来效率并不高,近似 \(O(n^2)\),但实际上它的理论复杂度是 \(O(n)\)

为何?

对于每个 \(i\)
如果 \(i<=R\),那么直接 \(O(1)\) 计算 \(r[i]\)
如果 \(i>R\),那么会用 \(O(len)\) 向右扫描 \(len\)个单位,所以此时 \(R\) 会向右移动 \(len+1\) 的单位。
\(R\) 最多只会移动 \(n\) 个单位,因此 \(Manacher\) 算法时间复杂度是线性的:\(O(n)\)


【例题】


\[ QAQ \]


六.【字典树(Trie)】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


七.【AC自动机】

在树上看毛片(\(Tire\) 树)。

\(To\) \(be\) \(continued...\)


\[ QAQ \]


八.【后缀数组】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


九.【后缀自动机(SAM)】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


十.【回文自动机/回文树(PAM)】

\(To\) \(be\) \(continued...\)


\[ QAQ \]


转载于:https://www.cnblogs.com/Xing-Ling/p/11555054.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_38166905/article/details/102258530

智能推荐

皮皮虾小视频怎么去水印_歌乐软件的博客-程序员宅基地

皮皮虾小视频怎么去水印 在短视频操作中,视频修改的作用显得尤为重要,这里介绍几款常见的工具1,批量下载软件(短视频无水印下载)2,批量消重伪原创软件(视频深度消重伪原创处理)歌乐软件,专业自媒体系列软件研发。肯定有人会问,为什么我的作品突然无法投放了 在短视频日新月异的发展之下,搬运工作越来越考验技巧性。 工欲善其事必先利其器,软件的作用就显得尤为重要 批量下载,批量去水印,批量消重伪原创,让软件代替手工...

CUDA GPU架构-硬件和软件_SetDreamer的博客-程序员宅基地

掌握部分硬件知识,有助于程序员编写更好的CUDA程序,提升CUDA程序性能,本文目的是理清sp,sm,thread,block,grid,warp之间的关系。由于作者能力有限,难免有疏漏,恳请读者批评指正。  首先我们要明确:SP(streaming Process),SM(streaming multiprocessor)是硬件(GPU hardware)概念。而thread,block

PPT模板(淘宝花钱买来的,免费分享给大家)_马鹏森的博客-程序员宅基地

Y749-高品质PPT模版压缩版和未压缩版(内容一样)手机电脑都可以用综合PPT模板(未压缩版)地-址:http://m1page.com/s/9756ya必须用电脑下载综合PPT模板(压缩版)链接:https://pan.baidu.com/s/1WIB1O6fdCgHOZgzBMctVAQ提取码:yiyiY754Y-毕业答辩两个链接任选一个操作在线使用手机电脑都可以在线使用链接:https://pan.baidu.com/s/1jHDvO4oiHBJbF2lol8SXc...

sqlyog如何增删改查?_赵博林的博客-程序员宅基地_sqlyog增删改查

-- 创建数据库employeeCREATE DATABASE employee ;SHOW DATABASES ;USE employee ;-- 创建dept表CREATE TABLE dept(deptno INT(10) PRIMARY KEY,dname VARCHAR(20),loc VARCHAR (20))-- 查询dept表SELECT * FROM dept;-- 创建emp表CREATE TABLE `emp` ( `empno` INT(10) P

Numpy.argmax()_关关雎鸠ԅ(¯﹃¯ԅ)的博客-程序员宅基地

返回沿轴axis最大值的索引。Parameters:a : array_like 数组axis : int, 可选默认情况下,索引的是平铺的数组,否则沿指定的轴。out : array, 可选如果提供,结果以合适的形状和类型被插入到此数组中。Returns: index_array : ndarray of ints索引数组。它具有与a.shape相同的形状,其中axis被移除。&gt;&gt;&gt; aarray([[0, 1, 2], [3, 4, 5]])&gt;

算1 - n的阶乘和末6位(超详细)_chlllch的博客-程序员宅基地

这里需要一点数学知识:要计算只包含加法, 减法和乘法的整数表达式除以正整数n的余数, 可以在每步计算之后对n取余, 结果不变.神马意思呢这句话,就以本题为栗子计算(1!+2!+3!+...+n!)%1000000注意是每步计算之后对1000000取余,所以计算步骤可以如下:第1步:1!%1000000=1第2步:2!%1000000=2第3步:(1+2)%1000000=3第4步:3!%1000000=6第5步:(3+6)%1000000=9//第3步与第4步结果相加取余

随便推点

第三章 SQL高级查询_wyyvision的博客-程序员宅基地

                                  SQL高级查询章节目标嵌套子查询 聚合技术 排序函数 公式表表达式内容子查询作为查询条件使用     where--1.子查询作为条件--查询学号在王五前边的同学select * from StuInfo where stuid &amp;lt; (select stuid from StuInfo w...

Vue:VSCode中Vue代码的格式化问题解决(Code formatter)_Angular baby的博客-程序员宅基地_vetur.format.enable

VSCode自从更新之后,vue文件的html代码格式化就失效了,而且vue文件中的js ,css格式化样式都变了,原因在于都采用了prettier 来格式化,而配置文件中vetur.format.defaultFormatter.html 这个配置项的值为"none",我们需要对它重新进行设置。步骤一:首先确保你安装了vetur扩展插件。如下图,扩展里直接搜索vetur,安装下图的V...

ipad查看qq邮箱收件服务器,QQ邮箱Apple终端的邮箱管理解疑 | 我爱上QQ_jx zhong的博客-程序员宅基地

下面向大家介绍如何使用Mac上的邮件应用程序Mail创建QQ邮箱帐户,这里以iMac为例:1.在邮箱中启用IMAP服务。2.在Mail中新建QQ邮箱账户的第三步(创建过程见这里),点击“手动设置”,进入手工设置页面,在收件服务器设置中,“帐户类型”选择“IMAP”,“收件服务器”为imap.qq.com,如下图,然后点击“继续”。3.在弹出的是否需要加密传输密码的窗口中点击”继续”,进入到发件服...

Java工程师是做什么的 岗位职责都有哪些_千锋郑州的博客-程序员宅基地_编程工程师是做什么的

  随着电子产业的迅猛发展,Java技术也得到越来越广泛的应用,Java工程师随之也成为受欢迎的IT岗位。由于广泛的市场前景,较高的薪资待遇,让Java工程师成为非常有前途的职位,那么Java工程师主要是做什么的呢?下面一同来看看吧。  Java工程师,直白点来说,就好比你在做家具时,需要在模板上弄些花纹,但是需要一个工具来做花纹,Java也是一样,它只是一个工具。Java应用可以说是无处不在...

PEP 8 -- Style Guide for Python Code_请叫我算术嘉的博客-程序员宅基地

Indentation(缩进) Continuation lines should align wrapped elements either vertically using Python's implicit line joining inside parentheses, brackets and braces, or using ahanging indent[7]. When...

HTML 中的节点、元素、标签、标记的区别_liaowenxiong的博客-程序员宅基地_html中标记和标记有何区别

节点 Node节点是构成我们网页的最基本的组成部分,网页中的每一个部分都可以称为是一个节点例如: html标签、属性、文本、注释、整个文档等都是一个节点节点的类型节点是有类型的,不同节点的类型不同,按照大小关系分类如下文档节点表示的是 整个html元素节点表示的是 html 中的 标签属性节点表示的是 html标签 中的 属性文本节点表示的是 html标签 中的内容 文本节点最终是要映射成为 js 对象,程序员操作这些对象来改变网页属性和方法不同的节点具有不同的属性和方法

推荐文章

热门文章

相关标签