Похожие строки

Здесь Вы можете найти или обсудить множество различных алгоритмов, их описаний, реализаций на VB и других языках.
Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2751
Зарегистрирован: 26.06.2011 (Вс) 21:26

Похожие строки

Сообщение Qwertiy » 30.06.2011 (Чт) 22:39

Проверка, что строка может быть получена из другой вставкой/удалением/заменой не более чем одного символа за 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.
Последний раз редактировалось Qwertiy 01.01.2016 (Пт) 17:51, всего редактировалось 2 раз(а).

Хакер
Телепат
Телепат
Аватара пользователя
 
Сообщения: 16107
Зарегистрирован: 13.11.2005 (Вс) 2:43
Откуда: Казахстан, Петропавловск

Re: Похожие строки

Сообщение Хакер » 30.06.2011 (Чт) 22:54

1) Это и не вопрос по алогоритму, и не описание алгоритма.
2) Это какой-то чудной случай применения расстояния Левенштейна. Лучше бы о нём написал.
3) Дотнет, фи.
—We separate their smiling faces from the rest of their body, Captain.
—That's right! We decapitate them.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2751
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 30.06.2011 (Чт) 23:07

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

Antonariy
Повелитель Internet Explorer
Повелитель Internet Explorer
Аватара пользователя
 
Сообщения: 4824
Зарегистрирован: 28.04.2005 (Чт) 14:33
Откуда: Мимо проходил

Re:

Сообщение Antonariy » 01.07.2011 (Пт) 10:24

Qwertiy писал(а):никаких специфических нетовских функций не используется.
Особенно AndAlso.
Лучший способ понять что-то самому — объяснить это другому.

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2751
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 01.07.2011 (Пт) 11:12

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

Во-первых, это не функция, а во-вторых, от AndAlso можно легко избавиться, например так:
Код: Выделить всё
  Do While Not E1 And Not E2
    If Str1(E1) <> Str2(E2) Then Exit Do
    E1 -= 1
    E2 -= 1
  Loop

Qwertiy
Доктор VB наук
Доктор VB наук
 
Сообщения: 2751
Зарегистрирован: 26.06.2011 (Вс) 21:26

Сообщение Qwertiy » 01.01.2016 (Пт) 17:10

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

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


Вернуться в Алгоритмы

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

    TopList