Конференция VBStreets

Проверка, что строка может быть получена из другой вставкой/удалением/заменой не более чем одного символа за O(length).

Код: Выделить всё

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.

1) Это и не вопрос по алогоритму, и не описание алгоритма.
2) Это какой-то чудной случай применения расстояния Левенштейна. Лучше бы о нём написал.
3) Дотнет, фи.

1. Это алгоритм, который делает ровно то, что написано.
2. О расстоянии Левенштейна написано в Википедии. К тому же, это не частный случай его применения, т. к. его вычисление в общем случае делается за произведение длин. Здесь же делается проверка, что оно не превосходит 1, причём за линейное время.
3. А чем плох .NET? К тому же, легко переписать на VB6, т. к. никаких специфических нетовских функций не используется.

Qwertiy писал(а):никаких специфических нетовских функций не используется.

Особенно AndAlso.

Antonariy писал(а):Особенно AndAlso.

Во-первых, это не функция, а во-вторых, от AndAlso можно легко избавиться, например так:

Код: Выделить всё

  Do While Not E1 And Not E2
    If Str1(E1) <> Str2(E2) Then Exit Do
    E1 -= 1
    E2 -= 1
  Loop

Хакер писал(а):1) Это и не вопрос по алогоритму, и не описание алгоритма.

Теперь точно описание