检查字符串是否包含模式（关于一对一符号映射）

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 algorithm in 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! (factorial, number of all possible one to 26个字母之间的一个映射）

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

Answer 1

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

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

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

如果您想知道更新滚动哈希的确切数学：在从 Rabin-Karp 执行通常的 window-shift 更新后，如果添加的字符是小写字母并且在我们的 window 之前出现 j 个字符，则其字符值从 'm'到 'j'。对于素数 p，它对 'rolling hash modular sum' 的贡献从 m*(p^j) 变为 j*(p^j)，我们可以减去差值。您可以轻松计算任何 window 字符当前对哈希的贡献的任何滚动哈希也将起作用。

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

Answer 2

我不知道 Rabin-Karp，但这比 k=26 好！你提到。我正在将 onecompleX 之类的模式转换为 (.)(.)(.)(.)(.)(.)(.)X:

之类的正则表达式

import re

def solve(string, pattern):
    def replace(match, group={}):
        letter = match[0]
        if letter not in group:
            group[letter] = len(group) + 1
            return '(.)'
        return f'\{group[letter]}'
    regex = re.sub('[a-z]', replace, pattern)
    return bool(re.search(regex, string))

print(solve('justanexampleXstring', 'onecompleX'))
print(solve('AaBbDd', 'AaBa'))

输出（Try it online!）：

True
False

检查字符串是否包含模式（关于一对一符号映射）

Check if string contains pattern (with respect to one-to-one symbols mapping)

python

string

algorithm

hash

data-structures