首页 > 其他分享 >失配树学习笔记

失配树学习笔记

时间:2023-08-26 16:22:53浏览次数:35  
标签:前缀 dep 失配 ll 笔记 学习 fa border

传送门

考虑把原字符串先\(kmp\)一遍,求出以\(i\)结尾的前缀的最长\(border\),根据\(border\)的\(border\)还是\(border\)这个定理,我们在寻找前缀\(p\)和前缀\(q\)的最长公共\(border\)时,我们可以考虑运用这个定理,一直往前跳,找到最先一样的\(border\),这就是最长公共\(bordedr\),至于优化,我们可以使用倍增

细节,\(border\)不能是自身,所以在\(p\)跳完\(border\)后即使是为\(q\),也不能直接输出\(q\)。

上代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+50;
char s[N];
ll n,m,fa[N][22],dep[N],p,q;
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	fa[0][0]=fa[1][0]=0,dep[0]=0,dep[1]=1;
	for(ll i=2,j=0;i<=n;i++)
	{
		while(j!=0&&s[j+1]!=s[i]) j=fa[j][0];
		if(s[j+1]==s[i]) j++;
		fa[i][0]=j,dep[i]=dep[j]+1;
	}
	for(ll i=1;i<=21;i++)
	for(ll j=1;j<=n;j++)
	fa[j][i]=fa[fa[j][i-1]][i-1];
	scanf("%lld",&m);
	while(m--)
	{
		scanf("%lld %lld",&p,&q);
		if(dep[p]<dep[q]) swap(p,q);
		for(ll i=21;i>=0;i--) if(dep[fa[p][i]]>=dep[q]) p=fa[p][i];
		for(ll i=21;i>=0;i--) if(fa[p][i]!=fa[q][i]) p=fa[p][i],q=fa[q][i];
		printf("%lld\n",fa[p][0]);
	}
	return 0;
}

标签:前缀,dep,失配,ll,笔记,学习,fa,border
From: https://www.cnblogs.com/pengchujie/p/17658965.html

相关文章

  • Dirichlet 前缀和学习笔记
    传送门求\(b_k=\sum\limits_{i|k}{a_i}\)考虑\(i=p_1^k,j=p_1^{k+1}\),若我们已经求出了\(b_i\),则易知\(b_j=b_i+a_j\)然后根据上面的方法,考虑对于所有的\(k=p_1^{k1}p_2^{k2}...p_l^{kl}\),若\(j=p_2^{k2}...p_l^{kl}\),我们已经求出所有的\(c_k=a_j+a_{p1\timesj}+a_{p1^2\time......
  • 回文自动机(PAM)学习笔记
    传送门我认为理解回文自动机需要图,以\(abbaabba\)为例,它的回文树是这样的:令树上的每一个点为一个回文串,其中,\(1\)为根的树中的点回文串长度为奇数,且最中间的那个字母就是\(1\)连向其他点的的边的字母,而\(0\)为根的树中的点回文串长度为偶数。举点例子吧:点\(2\)的回文串为\(a\)......
  • c语言笔记6
    c语言笔记6(结构体,共用体,枚举,文件操作,makefile)1.结构体1.1结构体的概念结构体也是构造类型之一,由至少一个基本数据类型或构造类型组成的一种数据结构(集合),这种数据结构称之为结构体1.2结构体的定义使用结构体之前,先定义结构体,然后使用这个结构体时作为一种数据类型(......
  • 欧拉定理学习笔记
    欧拉定理:若\(gcd(a,m)=1\),则\(a^{\varphi(m)}\equiv1\pmod{m}\)证明:令\(r_1,r_2,···,r_{\varphi(m)}\)为模m下的一个简化剩余系,则\(ar_1,ar_2,···,ar_{\varphi(m)}\)也为模m下的一个简化剩余系,令\(f=r_1*r_2*···*r_{\varphi(m)}\),则有:\(f\equivar_1*ar_2*···*ar_{......
  • 学习 Linux 有哪些好处
    Linux是懒程序员的福音。接触Linux愈久愈发现这个特点。Linux下最受欢迎的产品都能很显著地降低时间成本。譬如Git,VIM,Emacs,Shell,Pacman(Arch的包管理),虽然很多软件在windows下也有相应的解决方案,但是,Linux的确是承载这些产品最完美的平台。用的久了的确会显著地提升工作效率,但因为Li......
  • 杜教筛学习笔记
    杜教筛学习笔记闲话感觉以前根本没学懂杜教筛,于是重学了一遍,写个笔记记录一下。前置知识依赖于迪利克雷卷积、莫比乌斯反演、整除分块相关知识。记号约定及基本性质约定:\(f*g\)表示\(f\)与\(g\)的迪利克雷卷积,即\((f*g)(n)=\sum\limits_{ij=n}f(i)g(j)\)。\(f\cdot......
  • 文章学习 | 大模型发展
    嬗变:大语言模型带来的人工智能新纪元|CCCF精选盖茨说:大语言模型创新的影响力可以与20世纪60年代的微处理器、80年代的个人电脑、90年代的互联网和21世纪初的苹果手机媲美。大模型的创新大语言模型是人工智能领域自然语言处理的一部分。在大语言模型出现之前,自然语言处理主......
  • 前端React学习路径
    在当今的软件开发领域,React已经成为一种广泛使用的JavaScript库,用于构建用户界面。它由Facebook开发并维护,具有高效、灵活和可扩展等特点,适用于各种类型的应用程序开发。本文将介绍前端React的学习路径,包括基本概念、核心功能、组件进阶、路由和状态管理、构建实践等方面,并结合代码......
  • 8.21-8.27学习总结博客七:Spark机器学习与实时处理
    博客题目:学习总结七:Spark机器学习与实时处理入门内容概要:学习使用Spark进行机器学习和实时数据处理的基本知识,了解Spark的机器学习库和实时处理框架。学习资源:推荐的Spark机器学习和实时处理教程、案例和学习资源。实践内容:通过编写Spark应用程序,实践使用Spark进行机器学习和实时......
  • Linux设备驱动开发详解——学习笔记
    Linux设备驱动概述计算机系统的运转需要软件和硬件共同参与,硬件是底层基础,软件则实现了具体的应用。硬件和软件之间则通过设备驱动来联系。在没有操作系统的情况下,工程师可以根据硬件设备的特点自行定义接口。而在有操作系统的情况下,驱动的架构则由相应的操作系统来定义。驱动存......