- Код: Выделить всё
Public Function AreSimilar(ByVal Str1 As String, ByVal Str2 As String) As Boolean
If Math.Abs(Str1.Length - Str2.Length) > 1 Then Return False
Dim S As Integer = 0, E1 As Integer = Str1.Length - 1, E2 As Integer = Str2.Length - 1, MinLength As Integer = Math.Min(E1 + 1, E2 + 1)
Do While S < MinLength AndAlso Str1(S) = Str2(S)
S += 1
Loop
Do While Not E1 AndAlso Not E2 AndAlso Str1(E1) = Str2(E2)
E1 -= 1
E2 -= 1
Loop
Return E1 <= S And E2 <= S
End Function
Пояснение алгоритма
Выделим наидлиннейший одинаковый префикс и наидлиннейший одинаковый суффикс (допускается, что один или оба найденных куска могут быть пустыми). Очевидно, что в этих кусках нам ничего менять не требуется. Центральной частью строки назовём участок между префиксом и суффиксом.
Рассмотрим несколько возможных ситуаций:
- (1) Префикс и суффикс совпадают со всей строкой. Строки были изначально одинаковы.
- Конкатенация префикс и суффикса даёт одну из строк. В таком случае для того, чтобы преобразование было возможно, необходимо и достаточно, чтобы центральная часть другой строки состояла из одного символа. Понадобится операция вставки или удаления.
- Центральная часть обеих строк состоит из одного символа. Нужна операция замены.
- Центральная часть хотя бы одной из строк состоит из нескольких символов. Преобразование невозможно.
- (2) Т. о. для различных строк необходимо и достаточно, чтобы центральная часть каждой из строк была не длиннее одного символа.
- Найдём индекс `S`, указывающий на следующий символ за одинаковым префиксом (возможно, длина строки плюс 1).
- Найдём индексы `E1` и `E2`, указывающие на символ, предшествующий одинаковому суффиксу в первой и второй строках соответственно (возможно, -1). Они могут различаться, т. к. длина строк может быть разной.
- В случае 1 получим `S=Length+1, E1=-1, E2=-1`.
- Центральная часть нулевой длины означает, что указатель конца будет стоять раньше указателя начала на 1 символ.
Центральная часть из одного символа будет представлена равными указателями конца и начала.
Во всех остальных случаях указатель конца будет больше. - Т. о. для (2) условие превратится в такое:
Для обеих строк указатель конца не превосходит указателя начала. - Заметим, что для одинаковых строк это условие так же выполняется.
- В качестве дополнительной оптимизации сначала проверим, что длины строк отличаются не более чем на 1.
