比較兩個字符串找到第一個和最後一個區別

Question

我有兩個字符串，我想查找第一個和最後一個區別。

即：

S1：「我幫一個非常漂亮的老太太過馬路。」

S2：'我幫助一位老太太過馬路。'

所需的輸出（由字檢查）：

[2,4] // 2 for 'a', 4 for 'nice'. 

因爲差異： '我幫averynice老太太過馬路。'

替代所需的輸出（通過字符檢查）：

[10,21] // 10 for space, 20 for 'e'. 

因爲不同的是：「我幫very nice老太太過馬路。」

我可以使用它們中的任何一個（或第三個選項），但是性能是一個問題，因爲有時我每秒執行幾十到幾百次這種檢查。

Answer 1

既然你沒有給我們看代碼，我能做的最好的就是建議你看看一些"String Metric"算法。這些都是在全球高性能應用中使用的經過驗證的算法。

我特別要求您闡明以下算法，這些算法是我最喜歡的。這是很容易實現他們，維基百科有一個很好的僞碼，他們還有：

1. http://en.wikipedia.org/wiki/Levenshtein_distance
2. http://en.wikipedia.org/wiki/Hamming_distance
3. http://en.wikipedia.org/wiki/Smith-Waterman_algorithm