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

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

Ответ

Алгоритм для случая, когда длины строк заранее не известны и в общем случае вообще не доступны, т.е. это потоки байт или файлы целиком не умещающиеся в памяти.
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 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
"); else printf("False
"); }