P12476 [集训队互测 2024] 研心

当你看向镜子时，是否会注意到自己背后的事物？我相信大部分人的关注点应该在自己的虚像上。 现在想象一面镜子，你能在镜子中看到自己所有可能的现状或未来，也许某个自己和你的朋友过着差不多的生活。你会在镜子中找到一个向往的自我，也许那是现在的自己，或者是更好的自己。但就如镜中的背景，也有很多的可能性是，其他的自我没有那么幸运，过的更普通，更辛苦。但不变的是，所有的可能性就是你自己。你从最开始便有着一双将可能性化为现实的翅膀。 不要忽略镜中的每一处细节，当你打碎这面镜子时，你会得到一双完整的翅膀。解开一切的束缚，蹬离地面，展翅高飞吧。

给定大小为 $n$ 的字符串序列 $S$ 和大小为 $m$ 的字符串序列 $T$，其中 $S$ 的第 $i$ 个字符串为 $S_i$，$T$ 的第 $j$ 个字符串为 $T_j$。 定义一个字符串的权值 $f(s)$ 为 $s$ 中最长奇回文子串的半径长度。例如 `aba` 的半径长度为 $2$，`ababa` 的半径长度为 $3$。 定义两个字符串的加法 $s + t$ 为把两个字符串拼接起来得到的新字符串。 求： $$\sum_{i=1}^{n} \sum_{j=1}^{m} f(S_i + T_j)$$

第一行输入两个正整数 $n,m$。 接下来 $n$ 行，输入 $n$ 个字符串 $S_i$。 再接下来 $m$ 行，输入 $m$ 个字符串 $T_j$。

输出一行，表示 $$\sum_{i=1}^{n} \sum_{j=1}^{m} f(S_i + T_j)$$ 的值。

### 样例解释 | 回文半径长度 | $T_1$ | $T_2$ | $T_3$ | | :---: | :---: | :---: | :---: | | $S_1$ | 1 | 2 | 1 | | $S_2$ | 2 | 3 | 2 | | $S_3$ | 2 | 3 | 3 | ### 数据范围 令 $s = \max(\sum |S_i|, \sum |T_i|)$。 本题共有 4 个子任务，只有通过子任务中所有数据才能获得所有分数。 | 子任务编号 | 分数 | 特殊条件 | | :---: | :---: | :---: | | 1 | 20 | $s \leq 5000$ | | 2 | 30 | $n = 1$ | | 3 | 20 | 保证所有字符在 $\{a, b\}$ 中随机 | | 4 | 30 | ~~依赖子任务 1, 2, 3~~ 还没配置子任务依赖 | 对于 100% 的数据，满足 $1 \leq n, m, s \leq 4 \times 10^5$，保证输入的字符串只包含小写字母。