回文自动机（PAM）
回文自动机（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\) 为右端的其他回文子串已经存在不必插入。
如上图所示，我们先不断跳 \(fail[cur]\) 找到第一个两侧是 \(s_i\)（X）的回文子串，将它对应的节点叫做 \(pos\)，接下来不断跳 \(fail[pos]\) 找到第一个（总共是第二个）两侧是 \(s_i\) 的回文子串，将它对应的节点叫做 \(pos'\)，将 \(pos,pos'\) 的 s[i]-'a' 子节点分别记作 \(tot\) 和 \(fail[tot]\)，其中 \(tot\) 可能需要新建，而 \(fail[tot]\) 无需新建。
接下来要解决的问题是如何判断两侧都是 \(s_i\)。如下图。
所以还需要对每个节点知道它对应回文串的长度 \(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） 相关文章
- 回文自动机
构造 和AC自动机及其类似 相比Manacher，它还可以统计某个回文子串的数量，结尾为\(i\)的回文串数量，大小（更方便） 节点 一个字符串总共有有\(n\)个本质不同的回文串 证明:对于每个右端点\(i\)，每次只有多出至多\(1\)个回文串...
- 回文自动机学习笔记
概述 回文自动机 \((PAM)\)，也叫回文树 可以用 \(O(n)\) 的时间复杂度求出一个字符串的所有回文子串 构建 回文自动机每个节点表示在它的父节点两侧各加上一个儿子字符 每个节点要记录一个 \(fail\) 指针，代表当前节点的最长回...
- 学习笔记第五十七节:回文自动机
学习笔记第五十七节:回文自动机 正题 由于回文自动机的代码十分的有趣,以至于半天都没看懂怎么实现. 为了解决广大苦困人民的烦恼,我决定写一篇 针对 代码的讲解 首先回文自动机有两个根,一个是偶根,一个是奇根. 偶根的长...
- Linux下PAM模块学习总结
Linux下PAM模块学习总结 在Linux中执行有些程序时，这些程序在执行前首先要对启动它的用户进行认证，符合一定的要求之后才允许执行，例如login, su等。在Linux中进行身份或是状态的验证程序是由PAM来进行的，PAM（Pluggable Authentica...
- 利用pam模块passwdqc限定linux用户密码强度
利用pam模块passwdqc限定linux用户密码强度 限定linux上的root密码强度本身就是一个伪命题。root用户可以直接操作/etc/shadow 修改密码。之所以要这么搞主要还是为了稍微提高一下系统的安全性，毕竟不是人人都知道shadow的改法。 windo...
- Linux如何通过PAM限制用户登录失败次数
现在很多地方都有限制用户登录的功能，Linux也是如此，当你登录失败多次后就可以限制用户登录，从而起到保护电脑安全的作用，通过PAM模块即可实现，下面随小编一起来了解下吧。 Linux有一个pam_tally2.so的PAM模块，来限定用户...
- Linux用户安全及Linux PAM验证机制
Linux用户安全及Linux PAM验证机制 一.Linux身份验证 1.用户与系统管理员 用户分为系统管理员与普通管理用户两大类。 每个用户在系统中都有唯一的用户名，是用户使用系统的凭证。 系统管理员(System Manager) 又称之为超级用户，账...
- PAM 的应用开发和内部实现源码分析
PAM 的应用开发和内部实现源码分析 本文主要通过对Linux PAM源代码进行分析，阐述了PAM的内部实现机制和怎样在应用程序中应用PAM进行认证，以及怎样开发PAM服务模块。 1引言 身份认证是操作系统安全的重要机制之一，系统通过...
- 基于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/
- 伪装在系统PAM配置文件中的同形异义字后门
伪装在系统PAM配置文件中的同形异义字后门 * 原创作者：fnpimr43017，本文属FreeBuf原创奖励计划，未经许可禁止转载 [var1] 受到 这篇文章 启发，故有此文。 目前主流的Linux发行版本都支持Unicode，这也给了利用同形异义字迷惑系统...
- 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 = _
- 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]\) 在新构造的串上是一个偶回文子串，...
- R语言 Kmeans聚类、PAM聚类、层次聚类、EM聚类
R语言 Kmeans聚类、PAM聚类、层次聚类、EM聚类 关注微信公共号：小程在线 关注CSDN博客：程志伟的博客 R版本：3.6.1 Kmeans函数：kmeans聚类 pam函数：PAM聚类 hclust函数：层次聚类 cutree函数：层次聚类解 Mclust函数：EM聚类 mclustBIC函数...
- 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
- CentOS6.3下vsftpd通过pam认证实现虚拟用户文件共享
CentOS6.3下vsftpd通过pam认证实现虚拟用户文件共享 FTP的全称是File Transfer Protocol(文件传输协议),就是专门用来传输文件的协议.它工作在OSI模型的第七层,即是应用层,使用TCP传输而不是UDP.这样FTP客户端和服务器建立连接前就要经过一...
- 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
- 通信系统仿真速成第5天：PAM系统在AWGN信道下的互信息
通信系统仿真速成第5天：PAM系统在AWGN信道下的互信息 信息论也好，通信原理也好，有个互信息的概念。 互信息(Mutual Information)是信息论里一种有用的信息度量。 它可以看成是一个随机变量中包含的关于另一个随机变量的信息...
- 如何修复 “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 开发版的一部
- 回文问题终极篇：最小代价构造回文串
回文问题终极篇：最小代价构造回文串 [var1] 学算法认准 labuladong 东哥带你手把手撕力扣???? 点击下方卡片即可搜索???? 读完本文，你可以去力扣完成第1312 题「让字符串成为回文串的最少插入次数」，难度 Hard 。 回文串就是正着...
- 分割回文串+最长回文子字符串
分割回文串+最长回文子字符串 分割回文串 解题方法:回溯法 1. 画出递归树 2. 根据递归树开始编码 1. 每个节点表示剩余的没有扫描到的字符串，产生分支是截取了剩余字符串的前缀； 如果前缀字符串是回文，则表示可以产生分...