【NOIP模拟】 20/02/13

蛮有意思的，考场肝了 $3.5h$3.5h 还好写出来了
我们考虑枚举回文串的中间点，一定是在一个串中，且在这个串中，一个端点要和它形成一个回文串
把原本就是回文串的特判掉（Infinity），那么我们钦定这个中间点后就有一个前缀或是后缀需要我们用其它串匹配，假如现在需要找一个串匹配我们的后缀，$n$n 很小，我们暴力枚举每一个串与之匹配

那么我们可以分类讨论：

暴力搜索显然不行，然后发现不管前面怎么匹配的，当前需要匹配的后缀一定，到末尾的最大长度是一定的，于是可以 $dp$dp， $dp[i][j][0/1]$dp[i][j][0/1] 表示需要匹配第 $i$i 个串第 $j$j 个位置的前缀或是后缀，到匹配完毕的最大长度，那么这样的复杂度是 $n^2L$n2L

脑子有些糊涂写了 $hash$hash，但发现居然要求类似 $lcp$lcp 的东西，那不是白给自己套一个 $log$log 吗，于是改成后缀数组，把所有串正反拼起来做一遍就可以了，这里的复杂度是 $\sum L*log(\sum L)$∑L∗log(∑L)
然后找到合法的中间点（它所在的回文串顶到端点）可以用 $manachar$manachar 预处理，顺便把在一个串中的回文串的答案求了

十分好写，只有 150 排 $Code$Code