首页 > 其他分享 >SAM/广义 SAM 非常偷懒的解释

SAM/广义 SAM 非常偷懒的解释

时间:2024-03-18 21:36:21浏览次数:25  
标签:ch SAM int len fa lst 偷懒 广义 np

这里是模板题 P6139。

进行了一个广义 SAM 的学习。离线部分 OiWiki 讲得很好,但是在线部分没有。我做一些补充。

首先 SAM 是什么?简单来说,

  • SAM 是一个有向无环图,节点是状态,对应一个 endpos(\(S\) 子串 \(t\) 的结尾位置集合)。边标有字符。

  • SAM 是有 \(t_0\) 初始状态,若干个结尾状态,是 \(\mathcal{O}(n)\) 的,\(\le 4\) 常数。

  • 本质不同字串个数=路径条数,可以 dp。

  • 一个状态中,定义 \(len(v)\) 为 \(t_0\) 到 \(v\) 的最长路径长度。

  • 一个状态中,定义 \(fa(v)\) 为 \(v\) 最长的后缀,使出现位置多余 \(v\)。

  • endpos 要么无交要么包含,可以构成后缀树。同一个 endpos 对应的字符串长度是一个区间,\([len(fa(v))+1,len(v)]\)。

我们当作你会 SAM 了(你去 OiWiki 看一下模板代码),广义 SAM 是什么呢?

首先看一下代码。

pos[0]=1;
for (int j=1; j<s.size(); j++){
	pos[j]=ins(s[j]-'a',pos[j-1]);
}

这个是主函数里的。因为是多个串,\(lst\) 是什么你只能是上一个的结尾,不能直接 ++tot 求得。

int ins(int c,int lst){
	// (1)
	if (t[lst].ch[c] && t[t[lst].ch[c]].len==t[lst].len+1){
		return t[lst].ch[c];
	}
	//
	int p=lst,np=++tot,fl=0;
	t[np].len=t[p].len+1;
	while (p && !t[p].ch[c]){
		t[p].ch[c]=np;
		p=t[p].fa;
	}
	if (!p){
		t[np].fa=1;
		return np;
	}
	int q=t[p].ch[c];
	if (t[q].len==t[p].len+1){
		t[np].fa=q;
		return np;
	}
	// (2)
	if (p==lst){
		fl=1;
		np=0;
		tot--;
	}
	//
	int nq=++tot;
	t[nq]=t[q];
	t[nq].len=t[p].len+1;
	t[q].fa=t[np].fa=nq;
	while (p && t[p].ch[c]==q){
		t[p].ch[c]=nq;
		p=t[p].fa;
	}
	// (3)
	return fl?nq:np;
	//
}

这个是拓展的部分。发现和普通的 SAM 相比,有 \(3\) 个不同的部分。为什么呢?

(1)处是因为如果有一个连续的转移,没必要新建了。

(2)处是因为:这个是有 \(c\) 的儿子,但是不是连续的,那么,我们只需要建新状态,不需要建 \(lst\rightarrow c\)。这个清空 \(np\) 然后 \(tot--\) 就可以了。

(3)处是因为:很容易理解,你删了 \(np\) 就得返回 \(nq\)。

然后就做完了。

Code
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 2e6+6;

struct sam {
	int fa,len,ch[26];
} t[N];

int tot=1,pos[N];

int ins(int c,int lst){
	if (t[lst].ch[c] && t[t[lst].ch[c]].len==t[lst].len+1){
		return t[lst].ch[c];
	}
	int p=lst,np=++tot,fl=0;
	t[np].len=t[p].len+1;
	while (p && !t[p].ch[c]){
		t[p].ch[c]=np;
		p=t[p].fa;
	}
	if (!p){
		t[np].fa=1;
		return np;
	}
	int q=t[p].ch[c];
	if (t[q].len==t[p].len+1){
		t[np].fa=q;
		return np;
	}
	if (p==lst){
		fl=1;
		np=0;
		tot--;
	}
	int nq=++tot;
	t[nq]=t[q];
	t[nq].len=t[p].len+1;
	t[q].fa=t[np].fa=nq;
	while (p && t[p].ch[c]==q){
		t[p].ch[c]=nq;
		p=t[p].fa;
	}
	return fl?nq:np;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	cin>>n;
	for (int i=1; i<=n; i++){
		string s;
		cin>>s;
		s=" "+s;
		pos[0]=1;
		for (int j=1; j<s.size(); j++){
			pos[j]=ins(s[j]-'a',pos[j-1]);
		}
	}
	ll ans=0;
	for (int i=2; i<=tot; i++){
		ans+=t[i].len-t[t[i].fa].len;
	}
	cout<<ans<<"\n"<<tot<<"\n";
	return 0;
}

标签:ch,SAM,int,len,fa,lst,偷懒,广义,np
From: https://www.cnblogs.com/SFlyer/p/18081465

相关文章

  • 论文解读(CGC)《Generating Counterfactual Hard Negative Samples for Graph Contrasti
    Note:[wechat:Y466551|可加勿骚扰,付费咨询]论文信息论文标题:GeneratingCounterfactualHardNegativeSamplesforGraphContrastiveLearning论文作者:论文来源:2023WWW论文地址:download 论文代码:download视屏讲解:click0-摘要图对比学习已经成为一种强大的无监督图......
  • Samba安装与使用
    Samba是在linux和UNIX系统上实现SMB的一个免费软件,由服务器及客户端程序构成。SMB(ServerMessagesBlock,信息服务块)是一种在局域网上共享文件和打印机的一种通信协议,它为局域网内的不同计算机之间提供文件及打印机等资源的共享服务。安装步骤:1.安装SMB应用:sudoapt-getinstal......
  • 基于广义正态分布算法改进的随机森林分类算法 - 附代码
    基于广义正态分布算法改进的随机森林分类算法-附代码文章目录基于广义正态分布算法改进的随机森林分类算法-附代码1.数据集2.RF模型3.基于广义正态分布算法优化的RF4.测试结果5.Matlab代码摘要:为了提高随机森林数据的分类预测准确率,对随机森林中的树木个数和最......
  • 【C++】【OpenCV-4.9.0】视频写入(VideoWriter,借助samples中的代码示例来进行学习)
    借助官方离线文档中的samples来理解VideoWriter文档位置:samples/cpp/tutorial_code/videoio/video-write/video-write.cpp注:需要提前下载openh264-1.8.0-win64.dll,然后放在Release文件夹下,否则无法正确对输出文件进行编码从而运行失败1#include<iostream>2#include......
  • EdgeSAM: Prompt-In-the-Loop Distillation for On-Device Deployment of SAM
    EdgeSAM:Prompt-In-the-LoopDistillationforOn-DeviceDeploymentofSAMEdgeSAM论文:https://arxiv.org/pdf/2312.06660.pdfEdgeSAM代码:https://github.com/chongzhou96/EdgeSAM1概述作者在对各种蒸馏策略进行深入剖析后,证实了task-agnostic的编码器蒸馏难以完全吸......
  • Samtec理念 | 测试在工程中的意义
    【摘要/前言】测试是所有制造过程的最后一个步骤,本应是非常重要的步骤,但却经常被忽视。测试不缜密的产品一旦流入市场,必然会摧毁质量声誉。在当今按键发文就能让全世界知晓的全民媒体时代,测试的重要性就更加彰显。与此同时,随着产品本身日渐复杂,受测产品的精密程度也随之攀升......
  • jmeter 取样器超时(Sample timeout) 设置
    1.取样器超(Sampletimeout)设置可以对采样器设置最大超时时间注:当设置为0时,0是个特殊值,相当于无限大,永不超时右键>>>添加>>>前置处理器>>>取样器超时(SampleTimeout) Sampletimeout(inmilliseconds):超时时间,默认时间为10s秒注:当设置为0时,0是个特殊值,相当于无限大,永......
  • A Sample of Ozaria Assessments and Quizzes
      HowTo:ShareLesson&ActivitySlideswithyourStudentsOzariaprovideseducatorswithturnkeycurriculumresources.TheseincludeLessonSlides,whichcanbefoundforeachmoduleintheCurriculumGuide: TheyalsoincludeActivitySlide......
  • ubuntu 22.04 安装samba服务
    1.安装软件sudoaptinstallsambasamba-common如果出现类似错误:dpkg:处理软件包samba-common-bin(--configure)时出错参考如下处理:sudosumv/var/lib/dpkg/info/var/lib/dpkg/info_bakmkdir/var/lib/dpkg/infoapt-getupdate&&apt-get-finstallmv/var/l......
  • (续)signal-slot:python版本的多进程通信的信号与槽机制(编程模式)的库(library) —— 强化学
    前文:signal-slot:python版本的多进程通信的信号与槽机制(编程模式)的库(library)——强化学习ppo算法库sample-factory的多进程包装器,实现类似Qt的多进程编程模式(信号与槽机制)——python3.12版本下成功通过测试......