生成一個字符串哈希來比較兩個子字符串

我有一個字符串「abcdbca」，我被指示切片兩個子陣列，說[0：3]和[4：7]，我得到字符串「abc」和「BCA」。我必須弄清楚這兩個子字符串是否相似（相同的元素，max_allowed_mismatch_error = 1）。生成一個字符串哈希來比較兩個子字符串

我試過計數排序，但並沒有那麼多的優化。所以，我雖然下一個更優化的方法可能是哈希。但我無法弄清楚哈希函數來準確地解決問題。我需要多次執行操作。

2017-06-04 ghost-sdk

這裏沒有問題。 –

特赦，我不明白？ –

哈希是不好的。

有兩種解決方案，一種是簡單的解決方案，即堅持子字符串長度相等並且計數等於字符，另一種是複雜的解決方案，即使用Needleman-Wunch等對齊算法。這將給出一個更強大的字符串相似性的想法。

2017-06-04 16:06:32

謝謝。我讀過它，但無法正確理解它。關於我上面提到的例子，你能解釋一下嗎？爲什麼你認爲哈希不好？ –

散列並不好，因爲兩個相似的字符串沒有相似的散列。對齊算法會將字符串的相似部分放在彼此的上方，並在必要時添加空位。所以AAB和CAA有AA對齊。然後，您將使用與天真方法相同的字符， –

但這不能正確回答問題。假設我有AAB和ACA，那麼他們將如何對齊？ –

回答