http://codeforces.com/gym/100548 题意： 切换面板：标签 标签 添加新标签  回文自动机、 给2个字符串，问2个字符串中，相等并且都是回文串的对数。 思路： 构建2个PAM.然后奇偶起点分别跑dfs即可。 PAM写成了模块化的形式orz /* *********************************************** Author :111qqz Created Time :2017年11月14日 星期二 20时22分15秒 File Name :G.cpp ************************************************ */ #include …

2160: 拉拉队排练 Time Limit: 10 Sec Memory Limit: 259 MB Submit: 1938 Solved: 743 [Submit][Status][Discuss] Description 艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带 …

http://acm.timus.ru/problem.aspx?space=1&num=1960 题意： 给一个字符串S,依次输出字符串S的所有前缀中，本质不同的回文串个数。 思路： 考虑构建PAM是一个增量算法...所以一边构建一边输出答案就好了。。。 某一时刻本质不同的回文串个数就是sz-1 (标号是从0..sz，一共sz+1个，减去2个根，所以是sz-1) /* *********************************************** Author :111qqz Created Time :2017年11月14日 星期二 01时01分03秒 File Name :2565.cpp …

Description 顺序和逆序读起来完全一样的串叫做回文串。比如acbca是回文串，而abc不是（abc的顺序为“abc”，逆序为“cba”，不相同）。 输入长度为n的串S，求S的最长双回文子串T,即可将T分为两部分X，Y，（|X|,|Y|≥1）且X和Y都是回文串。 Input 一行由小写英文字母组成的字符串S。 Output 一行一个整数，表示最长双回文子串的长度。 Sample Input baacaabbacabb Sample Output 12 HINT 样例说明 从第二个字符开始的字符串aacaabbacabb可分为aacaa与bbacabb两部分，且两者都是回文串。 对于100%的数据，2≤|S|≤10^5 …

http://acm.hdu.edu.cn/showproblem.php?pid=3948 题意： 给一个字符串，问本质不同的回文子串的个数。 思路： 考虑回文自动机。 我们知道，对于PAM上的一个节点，表示的就是一个本质不同的回文串。 UPDATE: 弃用了这种代码风格,新的写法见下面。 那么sz-2就是本质不同的回文子串个数了orz(减掉2是因为PAM有2个根，这2个根不表示回文串） #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> typedef long long LL; …

http://uoj.ac/problem/103 题意： 给你一个由小写拉丁字母组成的字符串 s。我们定义 s 的一个子串的存在值为这个子串在 s 中出现的次数乘以这个子串的长度。 对于给你的这个字符串 s，求所有回文子串中的最大存在值。 思路： 回文自动机，也叫回文树，但其实并不是树2333,所以以后还是称为回文自动机，缩写为PAM 学会了(?)SAM之后再看PAM真是简单得一逼。 学习笔记之后补。 对于这道题，PAM中一个状态的cnt表示的该状态所表示的回文串出现的次数 len表示的是该状态所表示的回文串的长度 UPDATE: 下面的代码风格太丑了，打算弃用。 更新的代码风格见最后 #include …

是14年才被提出来的算法... 先%一下该算法的作者：作者的codeforces页 接下来，老规矩，放一波资料： 参考博客1 codeforces上的讲解 20171115 update: emmmm，这篇是学习笔记是１６年９月写的。。。。一转眼13个月过去了啊。。 回文树，也叫回文自动机，简称PAM 学了SAM之后PAM简直是傻逼算法... 该算法时间和空间复杂度都是O(n) 这样的复杂度基于以下结论： 长度为n的字符串的本质不同的回文串的数目不超过n 因此状态数开到和字符串长度一样就可以了orz len表示某个状态所表示的回文串的长度 cnt表示某个状态所表示的回文串的数量 构建PAM的算法仍然是增量算法，在某一时刻，本质不同的 …