첫 번째와 마지막 차이를 찾는 두 문자열 비교

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