算法学习—————PAM回文自动机
2022/9/7 1:39:21
本文主要是介绍算法学习—————PAM回文自动机,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
时隔一年,第一次学习新的算法
原理和AC自动机差不多
基本思想:
-
两棵树分别代表奇偶
-
在一个回文串两边同时填上相同字符可以得到另一个回文串,以此构建两棵树
树上维护信息:
-
节点表示的回文串为当前位置的最长回文串
-
节点上维护当前位置最长回文串的长度,fail指针(当前回文串的最长回文后缀)
如何维护:
-
若可以扩展,长度+2 判断条件: s[pos-len-1] == s[pos],否则跳fail
-
如何维护fail? 找到第一个可以扩展的位置,连出c边的点即是fail的指向
代码为洛谷模板题
当前节点的答案为他的fail的答案+1(可想而知,感觉而知)
#include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #define O(x) cout<<#x<<" "<<x<<endl; #define B cout<<"Breakpoint"<<endl; using namespace std; int read(){ int x = 1,a = 0;char ch = getchar(); while (ch < '0'||ch > '9'){if (ch == '-') x = -1;ch = getchar();} while (ch >= '0'&&ch <= '9'){a = a*10+ch-'0';ch = getchar();} return x*a; } const int maxn = 5e5+10; struct node{ int len,fail,ch[30]; }pam[maxn]; char s[maxn]; int n,preNode = 2,tot = 2; int ans[maxn]; void insert(int pos){ if (pos > 1) s[pos] = (s[pos] - 97 + ans[preNode]) % 26 + 97; int c = s[pos]-'a'; while (s[pos - pam[preNode].len - 1] != s[pos]) preNode = pam[preNode].fail; if (pam[preNode].ch[c]) preNode = pam[preNode].ch[c]; else{ int nowNode = ++tot; pam[preNode].ch[c] = nowNode; pam[nowNode].len = pam[preNode].len + 2; if (preNode == 1) pam[nowNode].fail = 2; else{ for (preNode = pam[preNode].fail;s[pos - pam[preNode].len - 1] != s[pos];preNode = pam[preNode].fail); pam[nowNode].fail = pam[preNode].ch[c]; } preNode = nowNode; } ans[preNode] = ans[pam[preNode].fail] + 1; cout<<ans[preNode]<<" "; } int main(){ scanf ("%s",s+1); n = strlen(s+1); pam[1].len = -1,pam[2].len = 0; pam[2].fail = 1; for (int i = 1;i <= n;i++) insert(i); return 0; }
这篇关于算法学习—————PAM回文自动机的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行