cur*_*her 2 python string algorithm hash data-structures
我正在尝试解决以下问题：
\n\n\n检查字符串是否包含子字符串，该子字符串可以使用一对一小写符号替换（使用原始小写字母和新字母之间的双射）从模式中获得。
\n
我的字符串仅包含大写和小写英文字母（A\xe2\x80\x93Z, a\xe2\x80\x93z）。
\n例如：
\n\n\n正数：
\n
\n字符串： justanexampleXstring
\n模式： onecompleX
\n答案： true（anexampleX <-> onecompleX，使用的映射：a<->o，x<->c；大写不受映射影响）
\n负数：
\n字符串： AaBbDd
\npattern: AaBa
\n答案: false (pattern 中有两个重复的小写字母，原始字符串中没有重复的小写字母)
目前我正在考虑在多模式搜索设置中使用Rabin\xe2\x80\x93Karp算法：
\n\n\n搜索 k 模式的 na\xc3\xafve 方法是重复单模式搜索，花费 O(n+m) 时间，总计 O((n+m)k) 时间。相反，假设哈希表检查在 O(1) 预期时间内进行，上述算法可以在 O(n+km) 预期时间内找到所有 k 个模式。
\n
但是 na\xc3\xafve 检查所有可能的映射生成的字符串会导致 k= 26！（阶乘，26 个字母字母表之间所有可能的一对一映射的数量）
\n对当前方法的任何想法或优化将不胜感激。\n提前谢谢您！
\n您可以在相同的预期运行时间内对 Rabin-Karp 进行轻微更改来实现此目的（假设您的哈希函数满足通常的一致性要求）。这个想法是考虑什么类型的字符串相当于小写字母双射映射下的模式。首先，所有大写字母必须完全匹配，因此我们可以暂时忽略它们。对于小写字母，重要的是基于相等字符的索引划分。
例如，如果pattern = 'banana'，其长度为m=6，那么索引的分组将是3组，一组用于'b'索引，一组用于'a'，一组用于'n'索引。
（无序）分区则为([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)。我们可以通过在处理字符串时为每个小写字母实现“最后看到的”索引的哈希图来解决此问题。利用质数幂滚动哈希的系数之和，我们可以快速计算出所需的变化。
如果您想知道更新滚动哈希的确切数学：在从 Rabin-Karp 执行通常的窗口移位更新后，如果添加的字符是小写并且出现j在我们窗口中较早的字符，则其字符值从 'm' 变为'j'。对于 prime p，它对“滚动哈希模和”的贡献从 变为m*(p^j)，j*(p^j)我们可以减去差值。任何可以轻松计算任何窗口字符当前对哈希的贡献的滚动哈希也将起作用。
一个更有趣的问题是 Knuth-Morris-Pratt 或 Boyer-Moore 是否可以适应以类似的方式工作；我还没有找到类似的转换，因为我的算法依赖于滚动哈希。尽管如此，Rabin-Karp 的平均和最坏情况运行时间将保持不变。