3803: 通配符(第六轮01)
题目描述
白浅妹妹的文件系统中有 m 个文件（名字互不相同），但是白浅妹妹想要通过一个字符串 查到它们。
具体的， 白浅妹妹会给出一个字符串 S，长度为 n，包含小写英文字符和 *。白浅妹妹称， 对于一个字符串 t， 一个替换方案是合法的当且仅当将其中的所有字符 * 替换成一个任意 仅包含小写字符的字符串（可以为空），使得替换后的字符串与上述 m 个文件名之一相同。
白浅妹妹又说，她认为一个字符串 t 的美好度， 是其合法的替换方案总数。 现在她拿着字符串 S，想知道所有连续的子串的美好度和。
大样例： ex_wildfile.zip
输入
第一行两个正整数 n, m。
第二行一个仅包含小写英文字母和 * 的字符串， 表示 S。
之后的 m 行，每行一个字符串 ti，表示文件名。
输出
一行表示美好度和，对 998244853 取模。
样例输入 复制
3 1
a*b
ab样例输出 复制
4提示
【样例 1 输入】
3 1 a*b ab
【样例 1 输出】
4
【说明】
取子串a *，将其变成ab，合法。 取子串* b，将其变成ab，合法。 取子串*，将其变成ab，合法。
取子串a * b，将其变成ab，合法。
【样例 2 输入】
2 1 **
ab
【样例 2 输出】
5
【说明】
取子串` ∗ `（左侧或右侧）， 可变成`ab`。
取子串` ∗∗ `，可将两个` ∗ `分别替换为 Ø和 `ab` 、`a`和`b` 、`ab`和Ø。
【备注】
对于 10% 的数据，保证 S中全为小写字母。
对于另 10%的数据， ∣ ti ∣= 1。
对于另 20%的数据， n ≤ 200, ∑ ∣ ti ∣≤ 40。
对于另 30%的数据， n ≤ 104, ∑ ∣ ti ∣≤ 40。
对于 100%的数据， 1 ≤ n ≤ 5 × 10^4, 1 ≤ ∑ ∣ ti ∣≤ 1000。