QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 2048 MB Total points: 100
[+6]
统计

题目背景

当你看向镜子时,是否会注意到自己背后的事物?我相信大部分人的关注点应该在自己的虚像上。

现在想象一面镜子,你能在镜子中看到自己所有可能的现状或未来,也许某个自己和你的朋友过着差不多的生活。你会在镜子中找到一个向往的自我,也许那是现在的自己,或者是更好的自己。但就如镜中的背景,也有很多的可能性是,其他的自我没有那么幸运,过的更普通,更辛苦。但不变的是,所有的可能性就是你自己。你从最开始便有着一双将可能性化为现实的翅膀。

不要忽略镜中的每一处细节,当你打碎这面镜子时,你会得到一双完整的翅膀。解开一切的束缚,蹬离地面,展翅高飞吧。

题目描述

给定大小为 n 的字符串序列 S 和大小为 m 的字符串序列 T,其中 S 的第 i 个字符串为 SiT 的第 j 个字符串为 Tj

定义一个字符串的权值 f(s)s 中最长奇回文子串的半径长度。例如 aba 的半径长度为 2,ababa 的半径长度为 3。

定义两个字符串的加法 s+t 为把两个字符串拼接起来得到的新字符串。

ni=1mj=1f(Si+Tj)

样例输入输出

样例输入

3 3
a
aba
aaba
b
ba
ab

样例输出

19

样例解释

回文半径长度 T1 T2 T3
S1 1 2 1
S2 2 3 2
S3 2 3 3

数据范围

s=max

本题共有 4 个子任务,只有通过子任务中所有数据才能获得所有分数。

子任务编号 分数 特殊条件
1 20 s \le 5000
2 30 n=1
3 20 保证所有字符在 \{a, b\} 中随机
4 30 依赖子任务 1, 2, 3

对于 100% 的数据,满足 1 \le n,m,s \le 4\times10^5,保证输入的字符串只包含小写字母。