C — как сделать замену подстроки в строке (руками)?

Question

[okeyndell]

Потребовалось руками, без использования strings.h написать функцию замены подстроки в строке (первое вхождение). Мой код:

int strlength(const char *str) {
    int i = -1;
    while(str[++i]);
    return i;
}
void copyToAnotherString(const char* str1, char* str2) {
    for (int i = 0; i < strlength(str1); i++) {
        str2[i] = str1[i];
    }
}

char *replaceSubstring(const char* str1, const char* sub, const char* to) {
    int string_size = strlength(str1);
    int sub_size = strlength(sub);
    int to_size = strlength(to);

    int temp = sub_size-to_size;

    int subIndex = 0;
    char *result;

    if (sub_size > to_size) {
        subIndex = startsof(str1, sub);
        result = malloc(string_size + sub_size - to_size);
        copyToAnotherString(str1, result);
        for (int i = subIndex; i < temp; i++) {
            result[i] = to[sub_size-to_size++];
        }
    } else {
        subIndex = startsof(str1, sub);
        result = malloc(string_size + to_size - sub_size);
    }


    return result;
}

Суть проблемы в том, что он заменяет первые 2 символа в строке.

Comments

[mayton2019]

Никогда не понимал такого трюкачества.

int strlength(const char *str) {
    int i = -1;
    while(str[++i]);
    return i;
}

Если написать как пишут в консервативных языках, с телом цикла и проверкой условия отдельно и если ассемблерный выход будет одинаковый - то значит компиллятор реально умнее нас и все наши трюки устарели на 30 лет. Впрочем это моё ворчание. Просто я считаю что такое не должно проходить code-review.

А вот тут арифметика индексов вообще не нужна. Вам просто нужны указатели на начала строк и инкремент.

void copyToAnotherString(const char* str1, char* str2) {
    .....
}

А как это вы прогнозируете объём будущей строки?
result = malloc(string_size + sub_size - to_size);

Тут как раз чтоб узнать будущую длину строки - алгоритм нужно ВОСПРОИЗВЕСТИ.

По линии else - вообще непонятно. Аллоцировали грязную неинциализированную память и отдали на возврат. Зачем? Этож явный баг.

Кстати почитайте про КМП и Боуер-Мур для поиска подстрок.

Answer 1

[Wataru]

А что делает startsof()?

Даже если принять, что оно действительно ищет вхождение второй строки в первой - у вас там в каждой второй строчке ошибка.

malloc(string_size + sub_size - to_size);

Объясните мне, как вы получили вот это значение длины?

А дальше копирование у вас неправильно. Чтобы заменить строку-вхождение вам надо в ответ скопировать начало str1 до вхождения, потом скопировать to, потом скопироваать конец строки str1, после вхождения. Это должны быть три параллельных цикла. У вас в одной ветке их 2 (один в функцию бесполезную спрятан), в другой - только 1.

Answer 2

[res2001]

1. Не правильно вычисляете размер будущей строки в первом случае. В первом случае результирующая строка будет меньше оригинальной, у вас же получается больше.
2. Не выделяете место под завершающий нулевой символ. Вообще завершающий ноль вы полностью игнорируете. Без него у вас в итоге получится не строка, а массив символов. Раз уж вы делаете все в ручную, то и завершающий ноль надо проставлять руками.
3. Согласен с Wataru на счет startsof и трех циклов.
4. Я бы сначала искал вхождение строки замены и только если оно найдено производил бы необходимые действия, в т.ч. и выделение памяти под новую строку. У вас же сейчас предполагается, что подстрока замены всегда найдется, что в общем случае не верно.
5. Что будете возвращать, если замены не будет? Будете просто выделять память под новую строку и возвращать новую строку аналогичную оригинальной? Или будете возвращать указатель оригинальной строки? Но тогда будет мешать квалификатор const для str1. А кроме того, если возвращать указатель на оригинальную строку, то что должен делать вызывающий код со старой строкой? Т.е. если замена была, то вы возвращаете новую строку и в вызывающем коде старую строку можно удалить. А если строка не найдена, то старую строку удалить нельзя, т.к. вы вернули указатель на нее же. В общем надо еще продумать как возвращать результат. Я бы на самом деле возвращал признак была замена или нет (или количество замен), а результирующий указатель надо возвращать в дополнительном параметре. Если замен нет, то либо указатель не возвращается, либо возвращается указатель на str1.
6. в качестве оптимизации:
for (int i = 0; i < strlength(str1); i++)
Вызываете на каждой итерации strlength.

Comments

[res2001]

5.1. Так же можно подумать на счет того, что бы производить замену "на месте" и только если результирующая строка больше - выделять память. Кстати, строка не обязательно должна занимать весь буфер, т.е. буфер под str1 вполне может быть больше строки в нем лежащей, поэтому есть смысл в параметрах передавать и размер буфера (не размер строки, смотрите строковые функции из стандартной библиотеке с суффиксом _s) и ориентироваться на него при вычислении необходимости релокации памяти.