Сторнирование строковой операции

Question

Итак, я возился со своими алгоритмами шифрования, когда эта проблема привлекла мое внимание:

Предположим, у вас есть строковая операция, заданная следующим псевдокодом:

string go_wacky(string input, int reps)
{
    string result = input;
    foreach (0..reps)
    {
        result = insert_substring_at(result, input, random_from_to(0, length(result));
    }
    return result;
}

Или, в точкеи щелкните по терминологии, скопируйте строку, затем повторите несколько раз, сделав следующее: переместите курсор в произвольную позицию в строке и нажмите «вставить».

С учетом выходной строки и повторов, как извлечь входную строку (кроме «обратного перебора», основанного на восстановлении списка символов исходной строки с использованием повторений и длины вывода)?

Answer 1

Мы можем найти символы входной строки, посчитав частоты всех символов и разделив на rep count + 1. Например, если a равно 12 раз на выходе, а количество повторов равно 2. Тогда входная строка содержится в выводе 2+1 и, следовательно, содержит 12/3 = 4 a.

Далее, посмотрите на первый символ вывода, это также первый символ ввода. Вычтите одно из его частоты.

Для следующего символа мы делаем ветку.

• Это начало ввода: просто продолжайте.
• или , это второй символ ввода. Уменьшите частоту и продолжайте.

Примерно такая же процедура для следующих символов.

Например, если вывод начинается с aa.... При чтении второго a ввод может быть a... и aa.... (Если частота a не равна 1.)

Я думаю, это должно быть довольно быстро. В случае, если все частоты едины, это O (n) с размером n выходной строки.

Answer 2

Я надеюсь, что это не слишком грубо, но я не вижу другого пути:

Возьмите первый символ вывода (назовите его a) и последний символ вывода (назовите его b).

Поиск выходных данных для подстрок длины len (output) / reps, начинающихся с a и заканчивающихся b.Это приводит к списку кандидатов.

Для каждого кандидата рекурсивно замените внутри вывода кандидата пустой строкой, т.е. output = output.replace (андидат, '')

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

Answer 3

Длина выходных данных = N повторов * Размер входной строки.

Это не гарантируется, если не будет лучшего понимания размера входной строки или числа повторений.

Answer 4

просто несколько случайных мыслей:

• вход полностью появляется хотя бы один раз на выходе.
• эта проблема может быть решена для "самой длинной подстроки" .