其他字符串算法学习笔记（持续更新）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了其他字符串算法学习笔记（持续更新），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7518字，纯文字阅读大概需要11分钟。

内容图文

关于字符串Hash和后缀自动机SAM可以转至我之前的博客，这里不再阐述。

这里主要介绍一些不怎么常用（至少不如SAM和Hash）的算法。

1.SA

~~模拟退火~~后缀数组（Suffix Array）是一种很奇妙的算法。主要原因是它可以做到在 \(O(n\log n)\) 时间内完成排序。

关于如何完成这个比较基础，具体可见洛谷日报。

而后缀排序的重点在于“字典序排序”的一些奇妙性质。所以对于一般字符串的字典序排序，以下性质也适用。

首先可以发现的是 \(\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j)),k\in[i,j]\)。这个比较显然~~主要我也不怎么会严格证明~~。具体可以见洛谷日报的证明。

考虑有了这个我们可以干什么。考虑这样一道题：按一定方式给定一堆字符串（总长度可能很大），问其中本质不同前缀的个数。

那么显然可以发现，相邻两字符串的 \(\operatorname{LCP}\) 就是他们本质相同的前缀。换句话说，除此之外的部分都是本质不同的。

而根据那个奇怪的性质，相邻两个字符串 \((x,x+1)\) 的 \(\operatorname{LCP}\) 一定 \(\geq (i,k),k\geq i+1\) 的 \(\operatorname{LCP}\)。所以显然成立。

但是这个相邻的 \(\operatorname{LCP}\) 怎么求呢？

其实是有一个很simple的 \(O(n)\) 求法。~~什么SA-IS？完全不会。~~

具体来说，我们可以求出第 \(i\) 个位置与字典序在它前面的串的 \(\operatorname{LCP}\) \(h_i\)。可以发现有 \(h_{i}=h_{i-1}+1\)。于是乎就均摊 \(O(n)\) 了。

那么我们可以做什么了呢？求本质不同子串！每个后缀的前缀唯一对应一个子串，所以直接减就好了。

例：本质不同子串

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 100010
using namespace std;
int b[N],sa[N],rk[N],a[N],id[N];
char s[N];
void SA_(int n,int m)
{
	for(int i=0;i<=m;i++) b[i]=0;
	for(int i=1;i<=n;i++) b[rk[i]]++;
	for(int i=1;i<=m;i++) b[i]+=b[i-1];
	for(int i=n;i>=1;i--) sa[b[rk[id[i]]]--]=id[i];
}
void SA(int n)
{
	int m=124;
	for(int i=1;i<=n;i++) rk[i]=s[i]-'0'+1,id[i]=i;
	SA_(n,m);int t=0;
	for(int p=1;p<n;m=t,t=0,p<<=1)
	{
		for(int i=1;i<=p;i++) id[++t]=n-p+i;
		for(int i=1;i<=n;i++) if(sa[i]>p) id[++t]=sa[i]-p;
		SA_(n,m); swap(id,rk); rk[sa[1]]=t=1;
		for(int i=2;i<=n;i++) rk[sa[i]]=(t+=id[sa[i-1]]!=id[sa[i]] || id[sa[i-1]+p]!=id[sa[i]+p]);
	}
}
int ht[N];
void get_ht(int n)
{
	for(int i=1,p=0;i<=n;ht[rk[i]]=p,i++)
	if(rk[i]!=1) for(p=p-!!p;sa[rk[i]-1]+p<=n && i+p<=n && s[i+p]==s[sa[rk[i]-1]+p];p++);
}
int main()
{
	int n;
	scanf("%d%s",&n,s+1);
	SA(n);
	get_ht(n);
	long long ans=1ll*n*(n+1)/2;
	for(int i=1;i<=n;i++) ans-=ht[i];
	printf("%lld\n",ans);
	return 0;
}
// 压行？怎么可能？这叫 建筑美（

看到这你或许会问：这个不是SAM也能做吗？而且SAM是 \(O(n)\) 的。

的确，绝大部分SA能做的SAM都能做，而且SAM跑得快、支持在线、还更好些（~~所以我学SA干什么~~）。

别急，这里还有一个SA的晋升版本：

2.后缀平衡树（好像不一定是这么叫的）

没想到吧，后缀平衡树居然不是后缀树变过来的（我也没想到）。

首先我们还是考虑一般情况：给定一个字符串 \(S\) 的一堆子串，每次问某个子串 \(s0\) 与其他每个串的 \(\operatorname{LCP}\) 最大是多少。动态修改子串集合。

这个可以怎么做？考虑使用平衡树套Hash。具体可以见Hash学习笔记中的一道口胡的题（里面好像还有一个强制在线）。

这个是 \(O(n\log^2 n)\) 的，虽然比较暴力已经足够优秀了。但是如果我们插入的字符串有一些规律可循，是不是有更快的做法。

题意

维护一个字符串，支持加一堆字符，删一堆字符，询问某个字符出现次数。强制在线。总字符长度 \(\leq 10^6\)。

出题人真的是丧心病狂。。。

AC自动机能过？那就强制在线。

SAM还能过？那就每次加一堆字符。

啥？两只 \(\log\) 艹过去了？那就开到 \(10^6\)。~~真·5步出题法~~。

显然我们需要一个更高妙的做法。考虑多一只 \(\log\) 的瓶颈在于每次判断字典序时必须 \(O(\log n)\) 处理。再加上判断 \(O(\log n)\) 次，所以总 \(O(\log^2 n)\)。

平衡树的 \(\log n\) 没办法优化，考虑优化判断字典序。可以发现，我们要加入的字符串 \(u\) 在加入前它的前缀一定已经出现过了，所以前缀和当前要比较的节点 \(p\) 均出现过。

可以发现，当前加入的字符串 \(u\) 除了最后一个字符之外其他都与前缀 \(u-1\) 完全一致，所以我们先暴力比较 \(u\) 与 \(p\) 的最后一个字符，如果相同意味着这个 \(u-1\) 和 \(p-1\) 的字典顺序决定了 \(u\) 与 \(p\) 的字典顺序。但是直接这样比较还是 \(O(\log n)\)。

考虑如果我们维护出了所有前缀的 \(rank\)，那么显然 \(rank\) 的相对顺序就对应最后的结果。但是我们不能直接维护rank，这样会平白多出一个 \(\log n\)。考虑我们只需要知道 \(rank\) 的相对顺序即可。考虑利用平衡树的性质，每个点取一个权值 \(v_i=\frac{L+R} 2\)，然后根据 \(v_i\) 将区间分为两段递归处理。可以发现，这样满足 \(v_{ls_u}< v_u< v_{rs_u}\)。

这样建树的时间复杂度 \(O(|S|\log |S|)\)。

考虑这题维护的东西：出现次数。

这个就很好办了。考虑差分，比如要查 \(\texttt{AB}\)，我们就查字典序在 \(\texttt{AA[}\) 和 \(\texttt{AB[}\) 之间的字符。（\(\texttt{[}\) 的字典序大于所有大写字母）。具体来说，由于后缀平衡树中不存在字符 \(\texttt{[}\) ，我们可以直接用字典序小于 \(\texttt{AB[}\) 的数量减去小于 \(\texttt{AA[}\) 的数量。

总时间复杂度 \(O(|S|\log |S|)\)，空间复杂度 \(O(|S|)\)。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 2000010
#define db double
#define alp 0.72
#define MAXD 1e16
using namespace std;
char str[N],s[N];
db v[N];
int ch[N][2],siz[N];
int swp[N],stot,rt;
void upd(int u){siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;}
void dfs(int u)
{
	if(!u) return;
	dfs(ch[u][0]),swp[++stot]=u;dfs(ch[u][1]);
	ch[u][0]=ch[u][1]=0;
}
void build(int &u,int l,int r,db lf=0,db rf=MAXD)
{
	if(l>r) return;
	int mid=(l+r)>>1;db mf=(lf+rf)/2;
	u=swp[mid];
	v[u]=mf;
	build(ch[u][0],l,mid-1,lf,mf),build(ch[u][1],mid+1,r,mf,rf);
	upd(u);
}
void reb(int &u,db lf,db rf)
{
	if(max(siz[ch[u][0]],siz[ch[u][1]])<siz[u]*alp) return;
	stot=0;dfs(u);
	build(u,1,stot,lf,rf);
}
int cmp(int x,int y){return s[x]==s[y]?v[x-1]<v[y-1]:s[x]<s[y];}
void insert(int &u,int k,db lf=0,db rf=MAXD)
{
	if(!u){siz[u=k]=1;v[u]=(lf+rf)/2;ch[u][0]=ch[u][1]=0;return;}
	if(cmp(k,u)) insert(ch[u][0],k,lf,v[u]);
	else insert(ch[u][1],k,v[u],rf);
	upd(u),reb(u,lf,rf);
}
void erase(int &u,int k)
{
	if(u==k)
	{
		if(!ch[u][0] || !ch[u][1]){u=ch[u][0]|ch[u][1];return;}
		int p=ch[u][0],las=u;
		for(;ch[p][1];las=p,p=ch[p][1]) siz[p]--;
		if(las==u) ch[p][1]=ch[u][1];
		else ch[p][0]=ch[u][0],ch[p][1]=ch[u][1],ch[las][1]=0;
		u=p;
		upd(u);
		return;
	}
	if(cmp(k,u)) erase(ch[u][0],k);
	else erase(ch[u][1],k);
	upd(u);
}
bool cmp_s(int u){for(int i=1;str[i];i++,u=u-!!u) if(str[i]!=s[u]) return str[i]<s[u];return false;}
int answer(int u)
{
	if(!u) return 0;
	if(cmp_s(u)) return answer(ch[u][0]);
	else return answer(ch[u][1])+siz[ch[u][0]]+1;
}
void get_c(char s[],int mask)
{
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		mask=(mask*131+i)%len;
		char t=s[i];
		s[i]=s[mask];
		s[mask]=t;
	}
}
char opt[7];
int main()
{
	int n,m,k,las=0;
	scanf("%d%s",&m,s+1);n=strlen(s+1);
	for(int i=1;i<=n;i++)
	insert(rt,i);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",opt);
		if(opt[0]=='D'){scanf("%d",&k);while(k --> 0) erase(rt,n),n--;continue;}
		scanf("%s",str+1);
		get_c(str+1,las);
		int l=strlen(str+1);
		if(opt[0]=='A') for(int j=1;j<=l;j++) s[++n]=str[j],insert(rt,n);
		else if(opt[0]=='Q')
		{
			reverse(str+1,str+l+1);
			str[l+1]='Z'+1,str[l+2]='\0';
			int ans=answer(rt);
			str[l]--;
			ans-=answer(rt);
			printf("%d\n",ans);
			las^=ans;
		}
	}
	return 0;
}
//压行？不存在的。

3.Lyndon 分解

首先定义 \(\text{Lyndon Word}\) ：所有后缀中字典序最小的。

具体来说，你需要把一个字符串分解为若干个 \(\text{Lyndon Word}\)，并且字典序最小。

具体证明先咕着。

这里先给出结论：

我们可以贪心处理。具体来说，我们枚举当前串左端点 \(i\)，循环串的左右端点 \([l,r]\)。我们比较 \(r+1\) 和 \(l\) 的字典序。如果 \(r+1\) 大，那么我们当前的分割还是可行的。

否则就是不可行。我们直接把 \(l\) 移回当前串的左端点即可。

复杂度 \((n)\)。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 5000010
using namespace std;
char s[N];
int p[N],t;
int main()
{
	scanf("%s",s+1);
	int n=strlen(s+1);
	for(int i=1,j=1,k=2;i<=n;j=i,k=i+1)
	{
		for(;k<=n && s[j]<=s[k];k++)
		{
			if(s[j]<s[k]) j=i;
			else j++;
		}
		for(;i<=j;i+=k-j) p[++t]=i+(k-j)-1;
	}
	int ans=0;
	for(int i=1;i<=t;i++) ans^=p[i];
	printf("%d\n",ans);
	return 0;
}

更新至 9.29

内容总结

以上是互联网集市为您收集整理的其他字符串算法学习笔记（持续更新）全部内容，希望文章能够帮你解决其他字符串算法学习笔记（持续更新）所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/624187.html

来源：【匿名】

【上一篇】2 - SAT算法【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【其他字符串算法学习笔记（持续更新）】教程文章相关的互联网学习教程文章

算法导论学习笔记(2)－归并排序

今天学习了算法导论上的归并排序算法，并且完成了在纸上写出伪代码，以前就学过归并但是理解的不够透彻，以前还一直困惑：为什么明明归并排序比快排的时间复杂度更稳定，为什么库函数不用归并而用快排，现在知道原因了，因为归并排序必须开额外的空间，而且空间开销还比较大，下面介绍算法：首先，归并排序用到了分治的思想，把大数据分成若干个小数据，然后再分别对小数据进行处理，最后把小数据合并成大数据。其次，归并排序用到...

【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine【代码】

扫雷玩得好还是有点好处的......这个题一开始像从后向前按照第一排的数字进行DFS 发现自己真傻,先不说这种情况下每个数字的填写情况很多, 还要处理相邻位置的问题。所以可以对每一位有没有地雷进行枚举。处理每一位的时候，要保证上一个数字是合理的，否则不用进行下去了，类似回溯，注意have变量的处理就好了。#include <iostream> #include <stack> usingnamespace std; //最长暗示dfs //遇到3 和 0 其实只有一种情况 //遇到2 和...

【视频编解码·学习笔记】7. 熵编码算法：基础知识 & 哈夫曼编码【代码】

一、熵编码概念：熵越大越混乱信息学中的熵：用于度量消息的平均信息量，和信息的不确定性越是随机的、前后不相关的信息，其熵越高信源编码定理：说明了香农熵越信源符号概率之间的关系信息的熵为信源无损编码后平均码长的下限任何的无损编码方法都不可能使编码后的平均码长小于香农熵，只能使其尽量接近熵与混乱程度：混乱度越高的信源，越难以被压缩，需要更大量的信息来表示其排列顺序熵编码基本思想：是使其前后的码字之间尽...

【算法学习笔记】85.破环为链序列DP 松弛+代价 SJTU OJ 1073 能量项链【代码】

和石子合并很像, 为了对环状进行处理, 我们可以把输入数据复制一份接连在后边. 这样在最后的结果枚举起点找最大即可.注意这里代价的计算, 因为我们的data[i]只记录了珠子的头珠子的尾部即是下一个珠子的头部.//因为计算dp[i][j]时需要用到dp[i][k] k比j小所以j顺序dp[k][j] k比i大所以i逆序 k插入即可for (int i = 2*n-1; i >=1 ; --i){for (int j = i; j <= 2*n; ++j){dp[i][j] = 0;for (int k = i; k < j ; ++k) dp[i][j] = ma...

【算法导论-学习笔记】以线性时间增长的排序——计数排序【代码】【图】

计数排序是一种能够达到运行时间能够线性时间θ(n)的排序算法。在排序算法里算是最快的算法之一，当然，他有很强烈的前提。下面开始介绍一下技术排序（Counting Sort）。算法思想计数排序假设n个输入元素中的每一个都是介于0到k之间的整数，此处k为某个整数。这样可以用一个数组C[0..k]来记录待排序数组里元素的数量。当k=O(n)时，计数排序的运行时间为θ(n).注：关于C[0..k]，用键值对描述的话，待排序元素是键，相同元素的个数是...

KMP算法学习笔记【代码】

KMP算法从零开始大部分来自他人博客，蒟蒻只是总结学习引言字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置.char *str = "bacbababadababacambabacaddababacasdsd"; char *ptr = "ababaca";暴力解法如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被...

数据结构学习笔记模拟算法1【代码】

猜数字 #include<stdio.h> #include<time.h> int main() {int n,m,i=0;srand(time(NULL));n=rand()% 100 +1;do{printf("输入所猜的数字:");scanf("%d",&m);i++;if(m>n)printf("错误！所猜的数太大了!\n"); else if (m<n) printf("错误!所猜的数太小了！\n");}while (m!=n);printf("答对了!\n");printf("共猜测了%d次。\n",i) ;if(i<=5)printf("你太聪明了,这么快就猜出来了!");else if(i>5)printf("还需要改进方法，以便更快猜出...

数据结构与算法之美专栏学习笔记-复杂度分析【代码】

复杂度分析什么是复杂度分析数据结构和算法解决是“如何让计算机更快时间、更省空间的解决问题”。因此需从执行时间和占用空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述性能问题，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模的增长关系。为什么要进行复杂度分析和性能测试相比，复杂度分析有不依赖执行环境、成本低、效率高、易操作、指导性强的特点。掌握复杂...

STL学习笔记（算法概述）【代码】【图】

算法头文件要运用C++标准程序库的算法，首先必须包含头文件<algorithm>使用STL算法时，经常需要用到仿函数以及函数配接器。它们定义域<functional>头文件中。算法的分类可以按以下分类方式描述各个STL算法：非变动性算法(nonmodifying algorithms)变动性算法(modifying algorithms)移除性算法(removing algorithms)变序性算法(mutating algorithms)排序算法(sorting algorithms)已序区间算法(sorted range algorithms)数值算法(n...

【算法学习笔记】72.LCS 最大公公子序列动态规划 SJTU OJ 1065 小M的生物实验1【代码】

非常简单的DP如果dp[i,j]表示从0到i 和从0到j 这两段的相似度，那么可以知道每个dp[i,j]是由三种状态转化过来的第一种当dna1[i]==dna2[j]的时候 dp[i-1,j-1] + 1 长度加1第二种否则从下面两个状态过来那就是dp[i][j-1] 和 dp[i-1][j]//注意因为是顺序遍历这两个都已经计算过取两者最大即可。#include <iostream> #include <cstring> #include <algorithm> usingnamespace std;//最长公共子序列长度 LCS dpchar dna1[1000+1...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 其他字符串算法学习笔记（持续更新）

其他字符串算法学习笔记（持续更新）

内容导读

内容图文

1.SA

2.后缀平衡树（好像不一定是这么叫的）

【模板】后缀平衡树

题意

3.Lyndon 分解

内容总结

内容备注

内容手机端

【其他字符串算法学习笔记（持续更新）】教程文章相关的互联网学习教程文章

算法导论学习笔记(2)－归并排序

【算法学习笔记】76.DFS 回溯检测 SJTU OJ 1229 mine【代码】

【视频编解码·学习笔记】7. 熵编码算法：基础知识 & 哈夫曼编码【代码】

【算法学习笔记】85.破环为链序列DP 松弛+代价 SJTU OJ 1073 能量项链【代码】

【算法导论-学习笔记】以线性时间增长的排序——计数排序【代码】【图】

KMP算法学习笔记【代码】

数据结构学习笔记模拟算法1【代码】

数据结构与算法之美专栏学习笔记-复杂度分析【代码】

STL学习笔记（算法概述）【代码】【图】

【算法学习笔记】72.LCS 最大公公子序列动态规划 SJTU OJ 1065 小M的生物实验1【代码】

机器学习笔记（十）EM算法及实践（以混合高斯模型（GMM）为例来次完整的EM）【图】

【算法学习笔记】32.计算几何求含最多给定点的直线 SJTU OJ 1350 穿越沙漠【代码】【图】

算法学习笔记递归之快速幂、斐波那契矩阵加速【图】

推荐算法学习笔记【图】

【算法学习笔记】树状数组【代码】【图】

字符串 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程