#P18400. Almost Prefix Concatenation

Almost Prefix Concatenation

Almost Prefix Concatenation

长度为 nn 的字符串 A=a1a2⋯anA=a_1a_2\cdots a_n 是字符 a1,a2,…,ana_1,a_2,\ldots,a_n 的拼接,其长度记为 ∣A∣|A|。类似地,字符串 A=a1a2⋯anA=a_1a_2\cdots a_n 与 B=b1b2⋯bmB=b_1b_2\cdots b_m 的拼接为 a1a2⋯anb1b2⋯bma_1a_2\cdots a_nb_1b_2\cdots b_m,记为 A+BA+B。

两个长度相同的字符串 A=a1a2⋯anA=a_1a_2\cdots a_n、B=b1b2⋯bnB=b_1b_2\cdots b_n 的“编辑距离”,在本题中定义为满足 ai≠bia_i\ne b_i 的位置 ii 的个数,即按位置比较的不同字符数。

字符串 BB 的前 kk 个字符(k≤∣B∣k\le |B|)组成的字符串称为它的长度为 kk 的前缀。若 ∣P∣≤∣Q∣|P|\le |Q|,且 PP 与 QQ 的长度为 ∣P∣|P| 的前缀之间的上述距离至多为 1,则称 PP 是 QQ 的一个 近似前缀。

给定两个只含小写英文字母的字符串 S,TS,T。请考虑把 SS 切分成若干个非空部分的所有方式,要求每一部分都是 TT 的近似前缀。对于每一种合法切分,计算部分个数的平方,求这些平方的总和,并对 998244353998244353 取模。

形式化地,若合法切分写成 S=P1+P2+⋯+PkS=P_1+P_2+\cdots+P_k,则要求输出

$$\left(\sum_{\substack{S=P_1+\cdots+P_k\\ |P_i|\ge1,\ P_i\text{ 是 }T\text{ 的近似前缀}}}k^2\right)\bmod998244353.$$

输入格式

第一行包含字符串 SS(1≤∣S∣≤1 000 0001\le |S|\le1\,000\,000),只含小写英文字母。

第二行包含字符串 TT(1≤∣T∣≤1 000 0001\le |T|\le1\,000\,000),只含小写英文字母。

输入只有一组数据。

输出格式

输出一行一个整数,表示所有合法切分的部分个数平方之和,对 998244353998244353 取模的结果。

样例 1

ababaab
aba
473

样例 2

ac
ccpc
5

样例说明

第一个样例 S=ababaabS=\texttt{ababaab}、T=abaT=\texttt{aba} 共有 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.$$