#P18400. Almost Prefix Concatenation
Almost Prefix Concatenation
Almost Prefix Concatenation
长度为 的字符串 是字符 的拼接,其长度记为 。类似地,字符串 与 的拼接为 ,记为 。
两个长度相同的字符串 、 的“编辑距离”,在本题中定义为满足 的位置 的个数,即按位置比较的不同字符数。
字符串 的前 个字符()组成的字符串称为它的长度为 的前缀。若 ,且 与 的长度为 的前缀之间的上述距离至多为 1,则称 是 的一个 近似前缀。
给定两个只含小写英文字母的字符串 。请考虑把 切分成若干个非空部分的所有方式,要求每一部分都是 的近似前缀。对于每一种合法切分,计算部分个数的平方,求这些平方的总和,并对 取模。
形式化地,若合法切分写成 ,则要求输出
$$\left(\sum_{\substack{S=P_1+\cdots+P_k\\ |P_i|\ge1,\ P_i\text{ 是 }T\text{ 的近似前缀}}}k^2\right)\bmod998244353.$$输入格式
第一行包含字符串 (),只含小写英文字母。
第二行包含字符串 (),只含小写英文字母。
输入只有一组数据。
输出格式
输出一行一个整数,表示所有合法切分的部分个数平方之和,对 取模的结果。
样例 1
ababaab
aba
473
样例 2
ac
ccpc
5
样例说明
第一个样例 、 共有 19 种合法切分:
- 1 种切成 3 部分:
ab + aba + ab; - 6 种切成 4 部分,例如
a + b + aba + ab; - 7 种切成 5 部分,例如
a + b + ab + a + ab; - 4 种切成 6 部分,例如
a + b + a + b + a + ab; - 1 种切成 7 部分:
a + b + a + b + a + a + b。
因此结果为
$$(3^2+6\cdot4^2+7\cdot5^2+4\cdot6^2+7^2)\bmod998244353=473.$$