logo AlgoBeat OnlineJudge
登录 注册

#215259. [AFOI 2025] D.谐音替换

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

时光荏苒,那个关于“谐音替换”的下午,依旧清晰地印在小 的脑海里。

那时的他,执着于精确的匹配:必须完全相同的子串,才能进行替换。然而,现实往往不尽如人意,细微的差别就足以让一切努力付诸东流。

多年以后,当小 再次翻开语言学笔记,他对“谐音”有了新的理解:何必苛求完全一致?只需拥有相同的前后,便已足够谐音。就像回忆中的点滴,不必完整重现,只需一个开头或一个结尾,便能串联起整个故事。


是一名喜欢语言学的算法竞赛选手。在语言学中,谐音替换是指将原有的字词替换为读音相同或相近的字词。小 发现,谐音替换的过程可以用字符串的前缀或后缀关系来进行描述。具体地,小 将谐音替换定义为以下字符串问题:

  • 字符串 的谐音替换,当且仅当 前缀,或 后缀
  • 记语言集合为 。字符串 的一个谐音三元组是指将 分成三个非空的连续段 (其中 表示字符串拼接),使得每一段 均是 中的某个字符串的谐音替换,每一种划分方案对应一个字符串三元组 ,我们称这个三元组为字符串 的一个谐音三元组。 两个谐音三元组 本质不同,当且仅当

现在给出 个字符串 作为语言集合,再给出 个字符串 作为待分析的语言资料。
请对于每个 ,帮助小 求出有多少种本质不同的谐音三元组方案。

输入格式

第一行包含两个整数 )。

接下来 行,每行一个字符串 ,表示语言集合中的单词。

接下来 行,每行一个字符串 ,表示待分析的资料。

输出格式

输出 行,其中第 )行包含一个非负整数,表示 有多少种本质不同的谐音三元组。

样例

样例输入 1

1 1
abbcabb
abbcabbcabb

样例输出 1

12

数据范围与提示

【样例1解释】

种本质不同的谐音三元组如下:

【数据范围】

为字符串 的长度,。对于所有测试数据,保证:

  • 对于所有 均仅包含大小写英文字母。
  • 对于所有 均仅包含大小写英文字母。
测试点编号 特殊性质
^
^ A、B
^ A
B
^
A
^ B

特殊性质 A:

特殊性质 B:对于所有 均以 z 结尾。对于所有 均不包含 z