Как можно реализовать алгоритм замены подстроки в строке?

Question

[LuVairo]

Нужно реализовать следующий алгоритм:
В исходной строке A нужно заменить все вхождения подстроки B на строку C
Делать так нужно до тех пор, пока в строке A не останется подстрок B.
Гарантируется однозначное декодирование.
Если решать через string.Replace(...) алгоритм займёт слишком много времени для больших строк.

Пример.
Вход: A = "abbacabba" B = "ba" C = "a"
Выход: aacaa

Comments

[Neonoviiwolf]

а ещё проверить, что после замены не образовались новые подходящие под замену подстроки

[Akina]

Алгоритм неполон и способен на некоторых исходных данных в зависимости от порядка поиска очередной подстроки давать разные результаты.

Пример.

A='ababa'
B='aba'
C='c'

Возможные результаты обработки:

1) 'abc'
2) 'cba'

[Wataru]

Дайте полное условие задачи. С ограничениями и примерами.

В общем случае быстрее string.replace не сделать.

[LuVairo]

Петя и Вася продолжают придумывать все новые и новые шифры. На этот раз они кодируют сообщение следующим образом: выбирается две подстроки a – подстрока, содержащаяся в исходном тексте и b – подстрока, на которую заменяется подстрока a. Это преобразование может применяться к сообщению некоторое число раз, если в шифруемом сообщение после предыдущей замены все еще осталось вхождение подстроки a. При передаче сообщения сначала записывается зашифрованный текст, а затем две подстроки a и b. Вам необходимо написать программу для расшифровки сообщений, закодированных таким образом. Алгоритм действий таков: необходимо заменить все вхождения подстроки b на подстроку a. Если после этой замены строка стала отличной от исходной и в ней все еще остались вхождения подстроки b, они снова заменяются на подстроку a. Так продолжается до тех пор, пока применение этого преобразование приводит к изменению строки.

Формат ввода
На вход программа получает три значения:

исходную строку;
подстроку, которую необходимо заменить в исходной строке;
подстроку, на которую необходимо заменить подстроку из исходной строки.
Каждое значение вводится с новой строки. Гарантируется, что входная строка декодируется однозначно, то есть не может быть тестов вида:
bbb
b
ab

[LuVairo]

Wataru, если в этой задаче использовать string.Replace(...), то алгоритм не пройдёт по времени

[Wataru]

LuVairo, Напишите ограничения, данные в условии.

[mayton2019]

Не знаю как реализован в шарпе string.Replace(...) но скорее всего это алгоритм из двух частей.
Первое - это собственно поиск строки. И второе - это генерация новой строки на основе замен старой.
Из алгоритмов поиска я помню 2 штуки. Кнута-Морриса-Пратта и Боуера-Мура. Вот можно в эту сторону
смотреть.

Я думаю что string.Replace(...) реализует вполне себе хороший алгоритм. И если автор хочет делать замены
в гигабайтных строках то стоит наверное глубже изучить предметную область. На что делаем упор? На очень
длинные строки? Будет ли вследствие замен строка сильно увеличена в размере? Какой аллоцировать объем
для билдера? (приблизительо). Будет-ли string.replace работать на регулярной основе.

Может имеет смысл строку индексировать? Но опять-же это можно обсуждать только зная данные.

Вобщем подытоживая. Знайте ваши данные.

[Wataru]

LuVairo,
Пока придумал плохой тест. Замена "abc"->"cccccccc...cab", текст "abcabcabc...abc". Тут квадратичное количество замен (и длина ответа). Введите такой, только с максимально допустимыми длинами (копируя c и abc). Как долго работает ваше решение с replace, какой time limit?

[Wataru]

LuVairo, Еще более страшный тест: "abc"->"bcbcbcbcbcbca". текст "aaaaaaaaaaaaaaaaaaabc". Тут, похоже, кубическое количество символов в ответе. Вообще, похоже, можно экспоненциально сложные тесты делать. Поэтому без разницы, через replace вы там делаете или еще как. Скорее всего у вас ошибка в коде и он виснет.

[Wataru]

LuVairo, Или еще мерзкий тест. Замена "ba" -> "ab". Фактически происходит сортировка вохдного текста из a и b. В этом примере видно, что нельзя заранее сказать, что какая-то часть текста станет постоянной после замены. Поэтому любые алгоритмы, которые как-то хитро собирают ответ по символьно не сработают.

Дайте ограничения в задаче и приведите ваш код.

[LuVairo]

Wataru, ответ по условию задачи передаётся через ToString() у соответствующего объекта,
поэтому такой код)

using System.Linq;
using System;

internal sealed class ReplacedString
{
    public string FinalString { get; set; }

    public ReplacedString(string line, string initial, string final) =>
        FinalString = Solve(line, initial, final);

    public override string ToString() => FinalString;

    private static string Solve(string line, string initial, string final)
    {
        var (borders, chars) = (GetSubarrayBorders(line, initial), line.ToCharArray());

        if (borders.Length == 0)
            return new string(chars);

        return Solve(
            new string(
                chars[0..borders[0]]
                    .Concat(final.ToCharArray())
                    .Concat(chars[borders[1]..chars.Length])
                .ToArray()
            ), initial, final
        );
    }

    private static int[] GetSubarrayBorders(string line, string subline)
    {
        var (chars, x) = (line.ToCharArray(), 0);

        while (x < chars.Length)
        {
            if (chars[x] == subline[0])
            {
                var status = true;

                for (var y = 1; y < subline.Length; y++)
                {
                    if (chars[x + 1] == subline[y]) x++;
                    else { status = false; break; }
                }

                if (status) return new[] { x - subline.Length + 1, x + 1 };
            }

            x++;
        }

        return Array.Empty<int>();
    }
}

[LuVairo]

Wataru,
Ограничение времени: 10 секунд
Ограничение памяти: 64Mb

[Wataru]

LuVairo, 1) у вас там выход за границы массива в GetSubarrayBorders, например, если последний символ в тексте совпадет с первым символом шаблона.

2) Постоянные преобразования в ToCharArray и new string - медленные.

3) Еще и рекурсия зачем-то прикручена.

4) Ваш алгоритм поиска подстроки квадратичный, если использовать встроенные алгоритмы, они будут сильно быстрее. Или пишите какой-нибудь алгоритм Кнута-Морриса-Пратта или Бойера-Мура.

Короче, избавьтесь от рекурсии и используйте встроенные функции работы со строками.

[Wataru]

LuVairo, И в третий раз спрошу, на всякий случай, вдруг с третьего раза вы заметите. скажите, уже, наконец, ограничения в задаче!

[Wataru]

LuVairo,

Ограничение времени: 10 секунд
Ограничение памяти: 64Mb

О, этого коммента еще не видел, пока свой писал. А ограничения на размер строк не даны разве?

[LuVairo]

Wataru, выше указал ограничения по времени и памяти

[Wataru]

LuVairo, А по размеру строк есть ограничения?

[LuVairo]

Wataru, нет

[LuVairo]

Wataru, написал вот два новых решения:

Рекурсивное (доходит до 9/10 теста (1.2 сек.) и завершается из-за превышения лимита памяти):

static string GetReplacedString(string line, string initial, string final)
{
    var index = line.IndexOf(initial);
    var chars = line.ToList();

    if (index < 0) return line;

    chars.RemoveRange(index, initial.Length);
    chars.InsertRange(index, final);

    line = new string(chars.ToArray());

    return GetReplacedString(line, initial, final);
}

Через цикл (доходит до 9/10 теста и завершается из-за превышения лимита времени)

static string GetReplacedString(string line, string initial, string final)
{
    while (line.Contains(initial))
    {
        var index = line.IndexOf(initial);
        var chars = line.ToList();

        if (index < 0) return line;

        chars.RemoveRange(index, initial.Length);
        chars.InsertRange(index, final);

        line = new string(chars.ToArray());
    }

    return line;
}

Может, всё дело в этом страшном предпоследнем тесте? Как думаете

[Wataru]

LuVairo, а может там initial и final совпадают? Кодируется однозначно, но код виснет.
Сделайте просто через string.Replace. Без ручных преобразований между массивами и строчками.

Answer 1

[Alexandroppolus]

Две идеи. Как применить, пока не очень понятно.
1) вместо строки использовать двусвязный список символов. Это поможет делать замены более экономно, не растрачивая память и не сдвигая толпу символов. Хотя, если строки В и С одинаковой длины, можно и массивом обойтись, но это частный случай, не думаю что надо с ним возиться.
2) сделали первый обход с заменами. Теперь новые вхождения заменяемой строки надо искать не по всей получившейся строке, а только там, где были замены (в районе левого и правого краев вставленной строки; так же условие гарантирует, что В не является подстрокой С). Точнее, даже так: сначала просмотреть строку А, найти (средствами стандартной библиотеки) все вхождения В и поместить их в очередь, потом перегнать строку А в двусвязный список, и далее по принципу обхода в ширину - берем из очереди позицию для замены, делаем замену, находим новые позиции замены (одну или две), добавляем в очередь, тут ещё проверить, что эти вновь добавленные позиции ни с кем не пересекаются..

Да, этот способ не позволяет сократить число замен, но это уже лучше, чем на каждом этапе заново искать позиции.

Дальнейшее ускорение - как то сократить число замен, поскипав промежуточные и вычислив результат, но тут много кейсов, и навскидку сказать трудно.

Comments

[LuVairo]

Большое спасибо, попробую реализовать вашу идею