唉,还是没有考虑清楚细节。
容易发现,一个双倍回文串必定是一个回文串,同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时,就可以同步更新答案。
但一开始我写出这样的判断:
- 1
- 2
- 3
// 完成第i个字符的最长回文的更新后 if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2) ans = max (ans, len[i]);
唉,还是没有考虑清楚细节。
容易发现,一个双倍回文串必定是一个回文串,同时前半段也是一个回文串。那么在使用Manacher算法求取每个字符对应的最长回文串时,就可以同步更新答案。
但一开始我写出这样的判断:
- 1
- 2
- 3
// 完成第i个字符的最长回文的更新后 if (len[i] % 4 == 0 && len[i - (len[i] >> 1)] == len[i] / 2) ans = max (ans, len[i]);