花莲县网站建设_网站建设公司_定制开发_seo优化

发现倒过来之后结构串的长度一定形如 \(1, 2, 3, ..., ans\)，思考 DP，设 \(f_i\) 为以 \(i\) 结尾最后一个串最长是多少，发现有 \(f_{i + 1} \le f_i + 1\)，因为 \(i + 1\) 的起始位置如果在 \(i\) 之前干脆把 \(i\) 的起始位置也调整到更前面。但其实这个结论不重要，我们每次枚举答案到底是多少，相当于看前面有没有合法的串，用一个哈希表存储一下就好了。

时间复杂度理论上 \(O(n\sqrt n)\)，但我卡不过去。