python - 检查字符串是否包含模式(关于一对一符号映射)

Question

我正在尝试解决以下问题:

Check, if the string contains substring, that can be obtained from pattern using one to one lower case symbols replacement (using bijection between original lower case letters and new letters).

我的字符串仅由大写和小写英文字母组成(A–Z、a–z)。

例如:

Positive:
string: justanexampleXstring
pattern: onecompleX
answer: true (anexampleX <-> onecompleX, used mapping: a<->o, x<->c; uppercase is not affected by mapping)
Negative:
string: AaBbDd
pattern: AaBa
answer: false (two repeated lower case letters in pattern and no repeated lower case letters in original string)

目前我正在考虑使用 Rabin–Karp multiple pattern search 中的算法设置:

A naïve way to search for k patterns is to repeat a single-pattern search taking O(n+m) time, totaling in O((n+m)k) time. In contrast, the above algorithm can find all k patterns in O(n+km) expected time, assuming that a hash table check works in O(1) expected time.

但是对所有可能映射生成的字符串的简单检查会导致 k=26!(阶乘，26 个字母表之间所有可能的一对一映射的数量)

对当前方法的任何想法或优化将不胜感激。提前致谢!

Answer 1

您可以在相同的预期运行时对 Rabin-Karp 进行轻微更改(假设您的哈希函数满足通常的一致性要求)。这个想法是考虑什么样的字符串等同于小写字母双射映射下的模式。首先，所有大写字母必须完全匹配，所以我们可以暂时忽略它们。对于小写字母，重要的是基于相等字符的索引划分。

例如，如果 pattern = 'banana'，其长度为 m=6，那么索引的分组将是 3 组，一组用于 'b' 索引，一组用于 'a'，以及一个给'n's。
然后(无序)分区为 ([0], [1, 3, 5], [2, 4])。现在，让我们找到等效的字符串表示形式。而不是这个分区，用到下一个相等字符的距离替换模式的每个小写字符(即，其分区组中的下一个较大值)，或 m，如果这是角色的最终外观。这意味着我们替换的 'banana' 字符串变成了
(6, 2, 2, 2, 6, 6);另一个长度为 m 的小写字符串具有相同的“替换”字符串当且仅当它与等值索引分组下的模式匹配时，当且仅当它们在字母双射下匹配时才与模式匹配。

我们可以使用 Rabin-Karp 的长度为 m 的滚动哈希，如上替换小写字母，并将大写字母映射到“m”以上的另一个数字范围(例如，m+1 到 m+ 26).唯一的问题是当我们的窗口向右滑动时，窗口中间的一个字符可能会改变值:
给定我们替换的字符串 'banana' (6, 2, 2, 2, 6, 6)，如果我们添加到字符串末尾的下一个字符是 'a'，我们替换的字符串为'ananaa' 是 (2, 2, 2, 6, 1, 6)。我们可以通过在处理字符串时为每个小写字母实现“最后一次看到”索引的 HashMap 来解决这个问题。使用 sum of coefficients of prime powers滚动哈希，我们可以快速计算出所需的更改。

如果您想知道更新滚动哈希的确切数学:从 Rabin-Karp 执行通常的窗口移位更新后，如果添加的字符是小写字母并且在我们的窗口中较早出现 j 个字符，则其字符值从“m”变为“j”。对于素数 p，它对“滚动哈希模和”的贡献从 m*(p^j) 变为 j*(p^j)，我们可以减去差异。您可以轻松计算任何窗口字符对哈希的当前贡献的任何滚动哈希也将起作用。

一个更有趣的问题是 Knuth-Morris-Pratt 或 Boyer-Moore 是否可以适应以类似的方式工作；我还没有找到类似的转换，因为我的算法依赖于滚动哈希。尽管如此，Rabin-Karp 的平均运行时间和最坏情况运行时间将保持不变。