Сравнивая две строки, находя первое и последнее различия

Question

У меня есть две строки, и я хочу найти первое и последнее отличие.

IE:

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