回文自动机(PAM)

作者:神秘网友 发布时间:2022-07-13 07:01:51

回文自动机(PAM)

构造

有两个空根 0 和 1,分别是偶根和奇根。以偶根为根的树存储所有偶数长度的回文串,奇根同理。
因为 Lemma. 「\(s\) 的本质不同回文子串总数是 \(O(n)\),所以存得下。

Proof

设以 \(i\) 为尾的最长回文子串左端是 \(l_i\),加入 \(s_{i+1}\) 后,得到了 \(l_{i+1}\)。对于 \(\subseteq [l_{i+1},i+1]\) 的所有以 \(i+1\) 为尾的回文子串,都会在 \([l_{i+1},i+1]\) 的头部已经出现一次。只有 \([l_{i+1},i+1]\) 有可能没出现过。

在回文树中,回文串是怎么存放的呢?奇根上的一条从空根 1 开始的链 1 ---a--- 2 ---b--- 3 ---c--- 4 代表了回文串 cbabc,偶根上的一条从空根上开始的链 1 ---a--- 2 ---b--- 3 ---c--- 4 代表了回文串 cbaabc。这与 AC 自动机直接自根而下存放不同。

回文树中每个节点有 \(fail_x\),表示 \(x\) 代表的回文串的最长共右端点回文子串对应的节点。

如何建树呢?
从左到右加入 \(s\) 中的字符,并用 \(cur\) 来维护当前的 \(s\) 所在的回文树中位置;我们每次的目标是将 \(s+s_i\) 的最长以 \(i\) 为右端回文子串插入回文树中(若还未出现),并将 \(cur\) 变成新插入的节点;以 \(i\) 为右端的其他回文子串已经存在不必插入。
回文自动机(PAM)
如上图所示,我们先不断跳 \(fail[cur]\) 找到第一个两侧是 \(s_i\)X)的回文子串,将它对应的节点叫做 \(pos\),接下来不断跳 \(fail[pos]\) 找到第一个(总共是第二个)两侧是 \(s_i\) 的回文子串,将它对应的节点叫做 \(pos'\),将 \(pos,pos'\)s[i]-'a' 子节点分别记作 \(tot\)\(fail[tot]\),其中 \(tot\) 可能需要新建,而 \(fail[tot]\) 无需新建。
接下来要解决的问题是如何判断两侧都是 \(s_i\)。如下图。
回文自动机(PAM)
所以还需要对每个节点知道它对应回文串的长度 \(len[tot]=len[pos]+2\)
考虑到当 \(s+s_i\) 的最长以 \(i\) 为右端回文子串只是 \(s_i\) 时无路可跳,我们必须将 \(fail[0]=1,len[1]=-1\) 才能让它正确地挂在了奇根下并获得正确的长度。

char s[N];int tot=1,pos,cur,trie[N][26],len[N],fail[N];//【tot=1】int getfail(int x,int i){while(i-len[x]-10||s[i-len[x]-1]!=s[i])x=fail[x];return x;}//mainfor(int i=0;in;i++){int b=s[i]-'a';pos=getfail(cur,i);if(!trie[pos][b]){fail[++tot]=trie[getfail(fail[pos],i)][b];len[tot]=len[pos]+2;trie[pos][b]=tot;}cnt[trie[pos][b]]++; //利用 cnt[trie[pos][b]]++ 并后面从 fail 树上累加上传还可以统计一个节点的出现次数cur=trie[pos][b];}

练习:Palindrome Characteristics

#include bits/stdc++.husing namespace std;const int N=5e3+5;//5e6+5 可以通过 |s|=5e6 的加强版int n,tot=1,pos,cur,len[N],fail[N],trie[N][26],num[N],half[N],cnt[N],buc[N];char s[N];vectorintxr,G[N];int getfail(int x,int i){while(i-len[x]-10||s[i-len[x]-1]!=s[i])x=fail[x];return x;}void dfs(int x,int h){xr.push_back(x),half[x]=xr[h];//维护一半回文所在位置if(x1)num[x]=(len[half[x]]==len[x]/2)*num[half[x]]+1;//并递推for(int y:G[x]){ int hh=h;while(hh+1!=xr.size()len[xr[hh+1]]=len[y]/2)hh++;dfs(y,hh);cnt[x]+=cnt[y];}xr.pop_back();}int main(){scanf("%s",s),n=strlen(s);fail[0]=1,len[1]=-1;for(int i=0;in;i++){int b=s[i]-'a';pos=getfail(cur,i);if(!trie[pos][b]){fail[++tot]=trie[getfail(fail[pos],i)][b];len[tot]=len[pos]+2;trie[pos][b]=tot;}cnt[trie[pos][b]]++;cur=trie[pos][b];}G[1].push_back(0);for(int i=2;i=tot;i++)G[fail[i]].push_back(i);dfs(1,0);for(int i=2;i=tot;i++)buc[num[i]]+=cnt[i];for(int i=n-1;i;i--)buc[i]+=buc[i+1];for(int i=1;i=n;i++)printf("%d ",buc[i]);}

回文自动机(PAM) 相关文章

  1. 回文自动机

    构造 和AC自动机及其类似 相比Manacher,它还可以统计某个回文子串的数量,结尾为\(i\)的回文串数量,大小(更方便) 节点 一个字符串总共有有\(n\)个本质不同的回文串 证明:对于每个右端点\(i\),每次只有多出至多\(1\)个回文串...

  2. 回文自动机学习笔记

    概述 回文自动机 \((PAM)\),也叫回文树 可以用 \(O(n)\) 的时间复杂度求出一个字符串的所有回文子串 构建 回文自动机每个节点表示在它的父节点两侧各加上一个儿子字符 每个节点要记录一个 \(fail\) 指针,代表当前节点的最长回...

  3. 学习笔记第五十七节:回文自动机

    学习笔记第五十七节:回文自动机 正题 由于回文自动机的代码十分的有趣,以至于半天都没看懂怎么实现. 为了解决广大苦困人民的烦恼,我决定写一篇 针对 代码的讲解 首先回文自动机有两个根,一个是偶根,一个是奇根. 偶根的长...

  4. Linux下PAM模块学习总结

    Linux下PAM模块学习总结 在Linux中执行有些程序时,这些程序在执行前首先要对启动它的用户进行认证,符合一定的要求之后才允许执行,例如login, su等。在Linux中进行身份或是状态的验证程序是由PAM来进行的,PAM(Pluggable Authentica...

  5. 利用pam模块passwdqc限定linux用户密码强度

    利用pam模块passwdqc限定linux用户密码强度 限定linux上的root密码强度本身就是一个伪命题。root用户可以直接操作/etc/shadow 修改密码。之所以要这么搞主要还是为了稍微提高一下系统的安全性,毕竟不是人人都知道shadow的改法。 windo...

  6. Linux如何通过PAM限制用户登录失败次数

    现在很多地方都有限制用户登录的功能,Linux也是如此,当你登录失败多次后就可以限制用户登录,从而起到保护电脑安全的作用,通过PAM模块即可实现,下面随小编一起来了解下吧。 Linux有一个pam_tally2.so的PAM模块,来限定用户...

  7. Linux用户安全及Linux PAM验证机制

    Linux用户安全及Linux PAM验证机制 一.Linux身份验证 1.用户与系统管理员 用户分为系统管理员与普通管理用户两大类。 每个用户在系统中都有唯一的用户名,是用户使用系统的凭证。 系统管理员(System Manager) 又称之为超级用户,账...

  8. PAM 的应用开发和内部实现源码分析

    PAM 的应用开发和内部实现源码分析 本文主要通过对Linux PAM源代码进行分析,阐述了PAM的内部实现机制和怎样在应用程序中应用PAM进行认证,以及怎样开发PAM服务模块。 1引言 身份认证是操作系统安全的重要机制之一,系统通过...

  9. 基于yubikey配合pam登录centos的安全认证登录

    基于yubikey配合pam登录centos的安全认证登录 下载对应的YubiKey Personalization Tool https://www.yubico.com/products/services-software/download/ 上传完成后如图所示: #yum -y install epel-release #yum -y install pam_yubico 确认/lib64/security/

  10. 伪装在系统PAM配置文件中的同形异义字后门

    伪装在系统PAM配置文件中的同形异义字后门 * 原创作者:fnpimr43017,本文属FreeBuf原创奖励计划,未经许可禁止转载 [var1] 受到 这篇文章 启发,故有此文。 目前主流的Linux发行版本都支持Unicode,这也给了利用同形异义字迷惑系统...

  11. PAM模块的backdoor实现与分析

    PAM模块的backdoor实现与分析 环境RHEL6.4 wget http://www.linux-pam.org/library/Linux-PAM-1.1.1.tar.gz tar xzvf Linux-PAM-1.1.1.tar.gz 主要修改 Linux-PAM-1.1.1/modules/pam_unix/pam_unix_auth.c /* verify the password of this user */ retval = _

  12. CF906E Reverses PAM+border

    题意: 戳这里 分析: 暴力: 对于PAM的DP题目,可能需要将题目转化一下,将原串变为 \(s_1t_1s_2t_2\dots s_nt_n\) ,这样对于一个需要翻转的区间 \([i,j]\) 满足 \(s_i=t_j,s_{i+1}=t_{j-1}\) 即区间 \([i,j]\) 在新构造的串上是一个偶回文子串,...

  13. R语言 Kmeans聚类、PAM聚类、层次聚类、EM聚类

    R语言 Kmeans聚类、PAM聚类、层次聚类、EM聚类 关注微信公共号:小程在线 关注CSDN博客:程志伟的博客 R版本:3.6.1 Kmeans函数:kmeans聚类 pam函数:PAM聚类 hclust函数:层次聚类 cutree函数:层次聚类解 Mclust函数:EM聚类 mclustBIC函数...

  14. vsftpd虚拟用户+mysql数据库管理用户pam认证

    vsftpd虚拟用户+mysql数据库管理用户,pam认证 一)安装vsftpd yum-yinstallvsftpdmysql-servermysql-develpam_mysql pam_mysql是epel源提供:安装epel方法 rpm -Uvh http: // dl.fedoraproject.org/pub/epel/6/x86_64/epel-release-6-8.noarch.rpm rpm--imp

  15. CentOS6.3下vsftpd通过pam认证实现虚拟用户文件共享

    CentOS6.3下vsftpd通过pam认证实现虚拟用户文件共享 FTP的全称是File Transfer Protocol(文件传输协议),就是专门用来传输文件的协议.它工作在OSI模型的第七层,即是应用层,使用TCP传输而不是UDP.这样FTP客户端和服务器建立连接前就要经过一...

  16. pam_cracklib_如何使用Cracklib在Linux中检查密码强度?

    pam_cracklib_如何使用Cracklib在Linux中检查密码强度? pam_cracklib Password security is important subject in IT. We call it password but actually it is a key to enter systems. Making authentication password-less by using key-based authentica

  17. 通信系统仿真速成第5天:PAM系统在AWGN信道下的互信息

    通信系统仿真速成第5天:PAM系统在AWGN信道下的互信息 信息论也好,通信原理也好,有个互信息的概念。 互信息(Mutual Information)是信息论里一种有用的信息度量。 它可以看成是一个随机变量中包含的关于另一个随机变量的信息...

  18. 如何修复 “fatal error: security/pam_modules.h: No such file or directory”

    问题 : 我尝试在 [某某 Linux 发行版] 上编译程序,但是出现下面的编译错误: "pam_otpw.c:27:34: fatal error: security/pam_modules.h: No such file or directory" 我怎样才能修复这个错误 缺失的头文件 'security/pam_modules.h' 是 libpam 开发版的一部

  19. 回文问题终极篇:最小代价构造回文串

    回文问题终极篇:最小代价构造回文串 [var1] 学算法认准 labuladong 东哥带你手把手撕力扣???? 点击下方卡片即可搜索???? 读完本文,你可以去力扣完成第1312 题「让字符串成为回文串的最少插入次数」,难度 Hard 。 回文串就是正着...

  20. 分割回文串+最长回文子字符串

    分割回文串+最长回文子字符串 分割回文串 解题方法:回溯法 1. 画出递归树 2. 根据递归树开始编码 1. 每个节点表示剩余的没有扫描到的字符串,产生分支是截取了剩余字符串的前缀; 如果前缀字符串是回文,则表示可以产生分...

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2021, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词