回文自动机（最基础版）

搞了一天多的回文自动机，总算勉强明白了一些，先记录一下最简单的
感谢详细题解：大佬题解
例题：P3649 [APIO2014] 回文串

#include

using namespace std;

typedef long long ll;

const int N = 300010;

int tot, n;
int ch[N][27];  //ch[i][s[j]]表示在编号为i的串的两端加上s[j]的新字符串的编号
int len[N];  //字符串编号
char s[N];
int fail[N];
int last;
int now;
int cnt[N];
ll ans;

inline int newnode(int x){  //建立一个新节点，长度为x 
	len[ ++ tot] = x;
	return tot;
}

inline int getfail(int x, int n){  //跳fail指针直到找到后缀回文为止
	while(s[n - len[x] - 1] != s[n]) x = fail[x];
	return x;
}

signed main()
{
	scanf("%s", s + 1);
	
	len[0] = 0, len[1] = -1;
	fail[0] = 1;
	tot = 1;
	s[0] = -1;
	
	for(int i = 1; s[i]; i ++ ){
		s[i] -= 'a';
		//找到可以回文的位置
		int p = getfail(last, i);  //返回的是节点编号 
		if(!ch[p][s[i]]){
			//如果有了转移就不用建了，否则要新建 
		    //前后都加上新字符，所以新回文串长度要加2
			now = newnode(len[p] + 2);
			//因为fail指向的得是原串的严格后缀，所以要从p的fail开始找起
			fail[now] = ch[getfail(fail[p], i)][s[i]];
			//记录转移
			ch[p][s[i]] = now;
		}
		++ cnt[last = now];
	}
	
	for(int i = tot; i; i -- ){
		cnt[fail[i]] += cnt[i];
		ans = max(ans,  (ll)cnt[i] * (ll)len[i]);
	}
	
	cout<<ans<<endl;
	return 0;
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62