时光荏苒,那个关于“谐音替换”的下午,依旧清晰地印在小 的脑海里。
那时的他,执着于精确的匹配:必须完全相同的子串,才能进行替换。然而,现实往往不尽如人意,细微的差别就足以让一切努力付诸东流。
多年以后,当小 再次翻开语言学笔记,他对“谐音”有了新的理解:何必苛求完全一致?只需拥有相同的前后,便已足够谐音。就像回忆中的点滴,不必完整重现,只需一个开头或一个结尾,便能串联起整个故事。
小 是一名喜欢语言学的算法竞赛选手。在语言学中,谐音替换是指将原有的字词替换为读音相同或相近的字词。小 发现,谐音替换的过程可以用字符串的前缀或后缀关系来进行描述。具体地,小 将谐音替换定义为以下字符串问题:
- 字符串 是 的谐音替换,当且仅当 是 的前缀,或 是 的后缀。
- 记语言集合为 。字符串 的一个谐音三元组是指将 分成三个非空的连续段 (其中 表示字符串拼接),使得每一段 均是 中的某个字符串的谐音替换,每一种划分方案对应一个字符串三元组 ,我们称这个三元组为字符串 的一个谐音三元组。
两个谐音三元组 和 本质不同,当且仅当 或 或 。
现在给出 个字符串 作为语言集合,再给出 个字符串 作为待分析的语言资料。
请对于每个 ,帮助小 求出有多少种本质不同的谐音三元组方案。