首页 > 其他分享 >[串串记录] PAM

[串串记录] PAM

时间:2023-03-24 11:34:18浏览次数:32  
标签:子串 自动机 串串 记录 最长 fail define PAM 回文

所谓回文自动机,就是一个能用来做回文问题的自动机。

Part 0. 待解决的问题

问一个串的本质不同回文串个数。

需要一个线形做法。

以下为 abbaabba 的回文自动机。

Part 1. 构造

考虑建一个树形结构。也就是回文树。

  • 增量法构造,在 \(s[0\sim i-1]\) 的回文树增加一个 \(s[i]\),只会增加一个节点。

    证明:考虑新产生的最长回文子串,所有新产生的回文串,都是最长回文子串的回文后缀。会发现这些新产生的都能一一对应翻转以后的前面插入过的短串。于是只会增加一个最新回文子串的节点。

于是本质不同回文子串的数目是 \(O(n)\) 的。

你会发现答案就是自动机点数 - 2.

  • fail 指针

和 AC 自动机类似,它的 fail 指针对应最长可匹配的前后缀,PAM 的 fail 则定义为最长回文后缀的位置。

设 \(s[0\sim i-1]\) 的最长回文子串在 PAM 上的节点为 \(x\)。

我们考虑 \(i - 1 - len[x]\) 和 \(s[i]\) 是否匹配,如果匹配,我们就知道这个是最长的了。

考虑 \(s[i]\) 的最长回文子串是 \(s[i-len[i]+1\sim i]\),我们要求 \(s[i-len[i]+2 \sim i - 1]\) 是满足 \(s[i-1-len[x]] = s[i]\) 的最长回文子串,不然和新加的最长是他矛盾。

如果匹配了, 我们就让新节点的 fail 指向匹配的点 \(x\)。

  • 细节
  1. fail[0] = 1,因为例如插入 \(aabbc\) 时,\(c\) 这个东西他是匹配不了啥的,但是能在奇数根连一条边,形如 \(1\to c\)。
    如果是 \(aabbcc\),他是有机会形成 \(cc\) 这样的在 \(0\) 这个根的串,我们需要让他尝试一下。
  2. 要分类讨论新点是否存在,如果存在,那么直接让 当前节点去到 这个存在的点。(自动机嘛,维护的是当前 \(s[0\sim i]\) 的最长回文子串对应节点)。
    不存在就新建节点。注意先更新 fail,方法是一直跳 \(fail[x]\) 的 fail,然后更新新点的 \(fail\)。然后设 \(siz[i]\) 表示自动机上 \(i\) 结尾的回文子串数目。
    \(siz[x] = siz[fail[x]] + 1\),表示 \(x\) 比他最长回文后缀多一个回文子串。
    要注意先更新 \(fail[x]\),在更新 fail[x] 的回文树 fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a'], tr[y][s[i]-'a'] = idx;
    这个很牛逼,插入 abbbc。比如说我在插入 \(b\) 时这么写。
    插入 b 时,cur 在 2 号点,我们 fail[cur] 在 1 号店,\(y = gfail(fail[cur], i) = 1\),如果已经新建了 \(tr[y][s[i]]\),那么这时 fail[idx] 会指向 idx。(tr[y][s[i]] = idx)。
    还有一个问题,为啥是从 fail[cur] 开始跳。
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
typedef long long ll;
typedef double db;
#define ep emplace_back
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define fout freopen("out.out","w",stdout);
#define fin freopen("in.in","r",stdin);
#define DE {cerr << "QAQ" << endl;}
#define dd(x) cerr << #x" = " << x << endl;
inline int read() {
	int x=0, v=1,ch=getchar();
	while('0'>ch||ch>'9') {
		if(ch=='-') v=0;
		ch=getchar();
	}while('0'<=ch&&ch<='9') {
		x=(x*10)+(ch^'0');
		ch=getchar();
	}return v?x:-x;
}
const int MAX = 5e5 + 5;
char s[MAX];
int fail[MAX],idx=1,tr[MAX][26],len[MAX],siz[MAX];
int gfail(int x,int i){
	while(i-len[x]-1<0||s[i]!=s[i-len[x]-1]) x=fail[x];
	return x;
}
signed main() {
	fin;
	scanf("%s", s);
	int n=strlen(s);
	fail[0]=1; len[1]=-1;
	int x=0,lastans=0;
	for(int i=0;i<n;++i){
		if(i) s[i]=(s[i]-97+lastans)%26+97;
		int y=gfail(x,i);
		if(!tr[y][s[i]-'a']){
			fail[++idx] = tr[gfail(fail[y], i)][s[i] - 'a']; 
			tr[y][s[i]-'a'] = idx;
			len[idx]=len[y]+2;
			siz[idx]=siz[fail[idx]]+1; 
		}
		x=tr[y][s[i]-'a'];
//		printf("%d ", lastans=siz[x]);
	}
	return 0;
}

标签:子串,自动机,串串,记录,最长,fail,define,PAM,回文
From: https://www.cnblogs.com/Lates/p/17250364.html

相关文章

  • bug记录
     时间格式问题导致查不到数据 2023-03-249:20:32查不到数据 2023-03-2409:20:32能查到数据   ......
  • 春哥甲(Hadoop雷点记录)
    “如果你也被春哥击倒,那么套上这个春哥甲吧!!!”这篇博客主要记录在学习Hadoop中遇到的各种雷点坑点!WordCountAndLen在这一节,我们开始尝试使用自定义的类型:WordCountAndLen......
  • 开发问题记录
    开发问题记录1.Vue父子组件传值延迟如何解决?问题描述:父组件中有一个通过异步的方式请求获取的数组,通过props传给子组件渲染页面,子组件页面空白。原因分析:由于父组件通过......
  • 学习记录-JAVA正则表达式
    正则表达式java匹配方法s.matches("JAVA");s.equals("JAVA");来询问该字符串是否匹配表达式正则表达式语法整行字符加上/表示为正则表达式/123/以下所有均省略//......
  • 接口测试平台 pity 搭建记录
    官方文档:https://wuranxu.github.io/pityDoc/Github:https://github.com/wuranxu/pity在线体验:http://121.5.2.74:8006/项目下载到本地,安装python依赖包。启动数据......
  • 个人常用sql记录
            CDATA区间使用 IF使用  CaseWhenThen的使用 ......
  • 任务悬赏提现多级分销信用记录h5小程序定制开发源码二开
    1. 用户可以自主发布接受任务用来获取赏金2. 用户可通过余额进行提现3. 用户可充值升级会员,以便进行接受更高福利的任务4. 设置有二级分销功能5. 设置有收支记录,更方便......
  • 记录--你还在傻傻的npm run serve吗?快来尝尝这个!
    这里给大家分享我在网上总结出来的一些知识,希望对大家有所帮助背景大家在日常开发中应该经常会有需要切换不同环境地址的情况。当一个项目代码切换环境地址时,vue-cli没......
  • 命令行实现自动清除浏览器的浏览记录(vbs)
    以下是前辈的经验,我借过来,学习学习,感谢感谢。先看目的,批处理是不行的用VBS很简单vbs例子如下,只需要保存为vbs文件即可,SetobjShell=CreateObject(“Wscript.Shell”......
  • vscode好用插件记录
    1.序言这里记录一下使用的好用的vscode插件,主要是给自己做一下备忘记录。2.插件通用插件Chinese(Simplified)(简体中文)LanguagePackforVisualStudioCodevsc......