Различаются ли строки не более чем на один символ?

Question

Есть две строки как проверить, что из одной можно сделать другую при помощи вставки, удаления или замены не более чем одного символа?

Answer 1

Минимальное количество операций вставки, удаления и замены символа, необходимое для преобразования одной строки в другую, называется расстоянием Левенштейна. В общем случае оно вычисляется за O(n*m), где n и m - длины строк.

Однако, в данном случае требуется не вычислить количество действий, а проверить, возможно ли сделать преобразование за 0 (строки изначально одинаковые) или 1 действие.

Рассмотрим две строки. Выделим наидлиннейший одинаковый префикс и наидлиннейший одинаковый суффикс (допускается, что один или оба найденных куска могут быть пустыми). Очевидно, что в этих кусках нам ничего менять не требуется. Центральной частью строки назовём участок между префиксом и суффиксом.

Рассмотрим несколько возможных ситуаций:

• (1) Префикс и суффикс совпадают со всей строкой. Строки были изначально одинаковы.
• Конкатенация префикс и суффикса даёт одну из строк. В таком случае для того, чтобы преобразование было возможно, необходимо и достаточно, чтобы центральная часть другой строки состояла из одного символа. Понадобится операция вставки или удаления.
• Центральная часть обеих строк состоит из одного символа. Нужна операция замены.
• Центральная часть хотя бы одной из строк состоит из нескольких символов. Преобразование невозможно.
• (2) Т. о. для различных строк необходимо и достаточно, чтобы центральная часть каждой из строк была не длиннее одного символа.

Несколько преобразуем этот алгоритм:

• Найдём индекс S, указывающий на следующий символ за одинаковым префиксом (возможно, длина строки плюс 1).
• Найдём индексы E1 и E2, указывающие на символ, предшествующий одинаковому суффиксу в первой и второй строках соответственно (возможно, -1). Они могут различаться, т. к. длина строк может быть разной.
• В случае 1 получим S=Length+1, E1=-1, E2=-1.
• Центральная часть нулевой длины означает, что указатель конца будет стоять раньше указателя начала на 1 символ.
  Центральная часть из одного символа будет представлена равными указателями конца и начала.
  Во всех остальных случаях указатель конца будет больше.
• Т. о. для (2) условие превратится в такое:
  Для обеих строк указатель конца не превосходит указателя начала.
• Заметим, что для одинаковых строк это условие так же выполняется.
• Если язык позволяет, то можно (в качестве дополнительной оптимизации) сначала проверить, что длины строк отличаются не более чем на 1.

А теперь в коде:

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
  Dim E1 As Integer = Str1.Length - 1, E2 As Integer = Str2.Length - 1
  Dim 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

Асимптотика линейная. В худшем случае (при одинаковых строках) делается по два полных прохода по каждой из строк.

Answer 2

Алгоритм для случая, когда длины строк заранее не известны и в общем случае вообще не доступны, т.е. это потоки байт или файлы целиком не умещающиеся в памяти.

int teststr(char *s1,char *s2)
{
 int k0=1,k1=1,k2=1;
 while(*s1==*s2 && *s1) {s1++; s2++;} // Ищем первое несовпадение
 char o1,o2;
 if(!*s1 && !*s2) return 1; // Строки равны
 do {
     o1=*s1++; o2=*s2++;
     k0=k0 && c1==c2;
     k1=k1 && c1==o2;
     k2=k2 && c2==o1;
     if(!(k0 | k1 | k2)) return 0; // Обнаружена ошибка (строки не преобразуемы)
    } while(o1 && o2);
 if( (!o1 && *s2) || (!o2 && *s1) ) return 0; // Расхождение длин строк более чем на 1
 return 2; // Строки преобразуемы за одно действие
}

Работает за один прямой проход строки до конца (если строки равны) или до первой обнаруженной ошибки. Т.е. максимальная сложность O(n).

Сначала идет сканирование строк до первого несовпадения. После этого начинается цикл идущий от точки несовпадения. Он сравнивает текущие символы двух строк, они равны в случае если предыдущее расхождение было заменой символа. А так же текущий символ одной строки с предыдущим символом другой строки, они равны в случаях если один символ был вставлен или удален и следовательно произошел сдвиг одной из строк. Одно из этих равенств должно сохранятся от точки когда было встречено первое расхождение и до конца строк.

Для любителей UTF-8 привожу полный код, нормально разбирающий данную кодировку с символами разной длины. Замечу, что он поймет любые символы, включая китайские иероглифы и т.п. Если нужна кодировка с символами фиксированной длины, большей чем байт, т.е. например UTF-16, то это решается проще, заменой char на short в предыдущем коде.

#include <stdio.h>
unsigned int utf32(char **s)
{
 unsigned char b=(unsigned char)**s;
 unsigned int code=0;
 int n=-1;
 if(b) (*s)++;
 if(! (b & 0x80) ) return b;
 b<<=1;
 while(b & 0x80) {b<<=1; n+=5; code=code<<6|**s & 0x3F; (*s)++;}
 code|= b << n;
 return code;
}
int teststr(char *s1,char *s2)
{
 int k0=1,k1=1,k2=1;
 unsigned int c1,c2,o1,o2;
 do {c1=utf32(&s1); c2=utf32(&s2);} while(c1==c2 && c1);
 if(!c1 && !c2) return 1;
 do {
     o1=c1; o2=c2;
     c1=utf32(&s1); c2=utf32(&s2);
     k0=k0 && c1==c2;
     k1=k1 && c1==o2;
     k2=k2 && c2==o1;
     if(!(k0 | k1 | k2)) return 0;
    } while(o1 && o2);
 if( (!o1 && c2) || (!o2 && c1) ) return 0;
 return 1;
}
int main()
{
 char *s1="Тестюabc";
 char *s2="ТестЦюabc";
 if(teststr(s1,s2)) printf("True\n");
 else               printf("False\n");
}

Answer 3

В PHP есть стандартная процедура levenshtein(), которая работает только с однобайтовыми кодировками. Но это поправимо.

Программа:

function near_cyr($s1,$s2){
    $str1 = $s1;
    $str2 = $s2;    
    $str1 = mb_convert_encoding($str1, "CP1251");
    $str2 = mb_convert_encoding($str2, "CP1251");
    return ((levenshtein($s1,$s2) == 1) 
         || (levenshtein($str1,$str2) == 1)) ? "рядом" : "не рядом";
};
printf("<br>%s ? %s - %s", $s1 = "карма", $s2 = "жара", 
    near_cyr ($s1, $s2));
printf("<br>%s ? %s - %s", $s1 = "карма", $s2 = "карман", 
    near_cyr ($s1, $s2));
printf("<br>%s ? %s - %s", $s1 = "карма", $s2 = "кара", 
    near_cyr ($s1, $s2));
printf("<br>%s ? %s - %s", $s1 = "карма", $s2 = "карта", 
    near_cyr ($s1, $s2));

Результаты:

карма ? жара - не рядом
карма ? карман - рядом
карма ? кара - рядом
карма ? карта - рядом