#P16810. [NWRRC 2024]Longest Common Substring

[NWRRC 2024]Longest Common Substring

题目描述

Lisa 编写了一个程序来解决最长公共子串问题。

对于某两个仅由字符 0 和 1 组成的字符串 s,ts,t,她使用程序找到了一个同时为 ss 和 tt 子串的最长字符串 ww。若最长公共子串不唯一,她任意选择了其中一个。

特别地,她得到的 ww 很短,长度至多为 33。

Lisa 还记得 ss 的长度 nn、tt 的长度 mm 以及字符串 ww,但已经忘记了 ss 和 tt 本身。

请计算有多少个有序字符串对 (s,t)(s,t) 满足:

  • ∣s∣=n|s|=n,∣t∣=m|t|=m;
  • s,ts,t 均只由 0 和 1 组成;
  • ww 是 ss 和 tt 的某个最长公共子串。

答案对 998 244 353998\,244\,353 取模。

注意,当 n=mn=m 且 s≠ts\ne t 时,(s,t)(s,t) 和 (t,s)(t,s) 被视为不同的字符串对。

输入格式

第一行包含三个整数 n,m,kn,m,k,分别表示字符串 s,t,ws,t,w 的长度。

第二行包含一个长度为 kk、仅由 0 和 1 组成的字符串 ww。

数据范围

1≤n,m≤100,1\le n,m\le 100, 1≤k≤min⁡(3,n,m).1\le k\le \min(3,n,m).

输出格式

输出一个整数,表示满足条件的有序字符串对 (s,t)(s,t) 的数量,对 998 244 353998\,244\,353 取模。

样例 1

2 2 1
1
6

样例 2

3 4 2
01
28

样例 3

7 5 3
110
399

样例 4

23 42 3
000
174497840

样例说明

在样例 1 中,所有满足条件的字符串对为:

$$(\texttt{01},\texttt{10}), (\texttt{01},\texttt{11}), (\texttt{10},\texttt{01}), (\texttt{10},\texttt{11}), (\texttt{11},\texttt{01}), (\texttt{11},\texttt{10}).$$

字符串 aa 是字符串 bb 的子串,当且仅当可以从 bb 的开头删除若干字符,再从结尾删除若干字符,得到 aa;删除的字符数均可为 00。