【记录】「COCI 2015.11」SAVEZ

https://www.luogu.com.cn/problem/P7861

阴。

回文匹配转换成前后对称字典树。

还有一个典错误：

这么写最后答案+1是部分错误

if (ch[p][j] == 0) { id ++; ch[p][j] = id; } else { dp[x] = max(dp[x], dp[rid[ch[p][j]]] + 1); } p = ch[p][j];

但这么写最后不+1是对的

if (ch[p][j] == 0) { id ++; ch[p][j] = id; } p = ch[p][j]; dp[x] = max(dp[x], dp[rid[p]] + 1);

这是因为第一个代码段当 ch[p][j] 有东西时就会执行，不管 ch[p][j] 是否是一个字符串的结尾。

所以如果当出现

aa

a

这样的数据时，a 会从 aa 的第一个字符转移，尽管值为 0（转移后为 1）。

这就相当于把它自己加上了，而最后答案又+1，所以错误。

正确代码：

#include<bits/stdc++.h> using namespace std; const int N = 2e6 + 10; char s[N]; map<int, map<int, int>> ch; int dp[N]; int id, rid[N]; int len; void ins(char *s, int x) { int p = 0; for (int i = 0; s[i]; i ++) { int j = (s[i] - 'A') * 26 + (s[len - i - 1] - 'A'); if (ch[p][j] == 0) { id ++; ch[p][j] = id; } p = ch[p][j]; dp[x] = max(dp[x], dp[rid[p]] + 1); } rid[p] = x; } int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; id = 0; ch.clear(); memset(dp, 0, sizeof(dp)); int ans = 0; for (int i = 1; i <= n; i ++) { cin >> s; len = strlen(s); ins(s, i); ans = max(ans, dp[i]); } cout << ans << "\n"; return 0; }