我正在嘗試解決以下問題：
檢查，如果字串包含子字串，可以使用一對一小寫符號替換（使用原始小寫字母和新字母之間的雙射）從模式中獲得。
我的字串只包含大寫和小寫英文字母 ( A–Z, a–z )。
例如：
Positive :
string: justanexampleXstring
pattern: onecompleX
answer: true (anexampleX <-> onecompleX, used mapping: a<->o, x<->c; 大寫不受映射影響)
Negative:
string: AaBbDd
pattern: AaBa
answer: false（模式中有兩個重復的小寫字母，原始字串中沒有重復的小寫字母）
目前我正在考慮在多模式搜索設定中使用Rabin-Karp演算法：
搜索 k 個模式的一種簡單方法是重復單模式搜索，花費 O(n m) 時間，總計 O((n m)k) 時間。相比之下，上面的演算法可以在 O(n km) 預期時間內找到所有 k 個模式，假設哈希表檢查在 O(1) 預期時間內作業。
但是對所有可能映射生成的字串進行簡單檢查會導致 k= 26！（階乘，26個字母字母表之間所有可能的一對一映射的數量）
對當前方法的任何想法或優化將不勝感激。先感謝您！
uj5u.com熱心網友回復：
您可以在相同的預期運行時間內對 Rabin-Karp 稍作更改（假設您的散列函式滿足通常的一致性要求）。這個想法是考慮什么樣的字串相當于小寫字母雙射映射下的模式。首先，所有大寫字母必須完全匹配，所以我們暫時可以忽略它們。對于小寫字母，重要的是基于相等字符的索引磁區。
例如，如果 pattern = 'banana'，其長度為m=6，那么索引的分組將是 3 組，一組用于 'b' 索引，一組用于 'a's，一組用于 '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). 我們可以通過在處理字串時為每個小寫字母實作“上次看到”索引的哈希圖來解決這個問題。使用滾動散列的素數冪系數之和，我們可以快速計算出所需的變化。
如果你想知道更新滾動哈希的確切數學：在從 Rabin-Karp 執行通常的視窗移位更新之后，如果添加的字符是小寫的并且j在我們的視窗中更早出現字符，它的字符值從 'm' 變為'j'。對于 prime p，它對“滾動哈希模和”的貢獻從m*(p^j)變為j*(p^j)，我們可以減去差值。任何可以輕松計算任何視窗字符對散列的當前貢獻的滾動散列也將起作用。
一個更有趣的問題是 Knuth-Morris-Pratt 或 Boyer-Moore 是否可以適應以類似的方式作業？我還沒有找到類似的轉換，因為我的演算法取決于滾動哈希。盡管如此，Rabin-Karp 的平均和最壞情況運行時間將保持不變。
uj5u.com熱心網友回復：
我不知道 Rabin-Karp，但這比 k=26 好！你提到過。我正在將模式onecompleX轉換為正則運算式，例如(.)(.)(.)(.)\1(.)(.)(.)\3X：
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'))
輸出（在線嘗試！）：
True
False
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/346252.html
上一篇：使用SymPy生成動態符號
下一篇：python將引數附加到函式呼叫