Сравнение подстрок с одним несоответствием - PullRequest
Новая
       3

Сравнение подстрок с одним несоответствием

0 голосов
/ 24 февраля 2012

Ниже приведен код для сравнения строки A и строки B с не более чем одним несовпадением, т. Е. ABC совпадает с ABX или AXC или XBC, но не совпадает с AXZ

Я проверял несколько случаев, носайт говорит, что дает неправильный ответ.Может ли кто-нибудь помочь выяснить, где этот код не работает?Кроме того, я был бы рад, если бы кто-то мог предоставить лучший алгоритм для той же проблемы.

TY 

int compare(string a,  int pos, string b)   {
int count = 0;
int length = b.length()-1;
int mid = b.length() /2;

if(pos+length >= a.length())
    return 0;

for(int i=0,j=pos;i<=mid;i++,j++)   {       
    if(i == mid)    {
        if(a[j] != b[i])
            count ++;
    }
    else    {
        if(a[j] != b[i])
            count ++;
        if(a[pos+length - i] != b[length -i]) 
            count ++;
    }
    if(count >= 2) return 0;
}
return 1;
}

1 Ответ

1 голос
/ 24 февраля 2012

Одна проблема состоит в том, что если b.length() является четным, то вы сравниваете a[pos + b.length() / 2] с b[b.length() / 2] дважды : один раз, когда i == mid - 1, и один раз, когда i == mid. Таким образом, что-то вроде compare("abcd", 0, "abbd") возвращает 0, поскольку оно считает расхождение 'c' -vs .- 'b' как два отдельных несоответствия.

Я рекомендую вам просто удалить всю логику, связанную с mid. Это не служит никакой другой цели, кроме огромного усложнения вашего кода. Если вы выполните итерацию прямо с 0 до b.length() - 1, вам будет намного лучше.

...