回文自动机(PAM)【模板】

>Link

luoguP5496

---

>Description

给出一个字符串 s s s ，求 s s s 中以每个字符结尾的回文子串个数。

---

>解题思路

回文自动机模板题
因为回文子串分为奇数和偶数两种，所以我们要建两棵树，以 1 1 1为根的为奇数树，以 0 0 0为根的为偶数树
回文子串是“折叠”挂在树上的，也就是从下往上读到根再往下读（奇数树上最上一层的字母只用读一次，所以初始得设 l e n 1 = − 1 len_1=-1 len1​=−1，这样不会多加）
f a i l fail fail指针指向最长回文后缀，所以我们要记录 l e n x len_x lenx​，表示以 x x x节点为结尾的最长回文串的长度，这样匹配时可以快速找到原串中与当前字符需要相等的字符（回文）

---

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 500010
using namespace std;

int n, tot, len[N], fail[N], sum[N], pos, t[N][30], last, lastans;
string s;

int get_fail (int x, int i)
{
	while (s[i] != s[i - 1 - len[x]] || i - 1 - len[x] < 0)
	  x = fail[x];
	return x;
}

int main()
{
	cin >> s;
	n = s.size();
	s = " " + s;
	tot = 1;
	len[1] = -1;
	fail[1] = fail[0] = 1;
	for (int i = 1; i <= n; i++)
	{
		s[i] = (s[i] + last - 97) % 26 + 97;
		int x = s[i] - 'a' + 1;
		pos = get_fail (pos, i);
		if (!t[pos][x])
		{
			fail[++tot] = t[get_fail (fail[pos], i)][x];
			len[tot] = len[pos] + 2;
			sum[tot] = sum[fail[tot]] + 1;
			t[pos][x] = tot; //一定要先找fail再赋值！！！不然会匹配到自己！！
		}
		pos = t[pos][x];
		printf ("%d ", last = sum[pos]);
	}
	return 0;
}