Reversing a string operation

So I was fiddling with my encryption algorithms when this problem caught my attention:

Suppose you have a string operation given by the following pseudocode:

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;
}

Or, in point-and-c开发者_高级运维lick terminology, copy the string, then reps times do the following: move the cursor to a random position within the string and hit paste.

Given the output string and reps, how to extract the input string (other than "reverse brute force" based on reconstructing the character list of the original string using reps and output length)?

We can find the chars of the input string, by counting the frequencies of all the chars and dividing by rep count + 1. For example, if a is 12 times in the output, and rep count is 2. Then the input string is contained 2+1 times in the output and thus contains 12/3 = 4 a's.

Next, look at the first char of the output, that is the first char of the input aswell. Subtract one from its frequency.

For the next char, we do a branch.

• It is the start of the input: Just continue.
• or, it is the second char of the input. Decrease the frequency and continue.

Pretty much the same procedure for the following chars.

For example, if the output starts with aa.... When reading the second a, the input can be a... and aa.... (Unless, the frequency of a is 1.)

I think this should be quite fast. In the case the frequencies are all one, this is O(n) with n size of the output string.

I hope this is not too brute-force, but I see no other way:

Take the first character of the output (call it a) and the last character of the output (call it b).

Search the output for substrings of length len(output)/reps starting with a and ending with b. This yields a list of candidates.

For each candidate replace recursively inside the output the candidate with an empty string, i.e. output = output.replace (candidate, '')

If after the last replacement, the result is an empty string you found the plain text.

just some random thoughts:

• the input appears completely at least once in the output.
• this problem may resolve to the "longest substring".

Length of the output = N repeats * size of the input string.

This isn't guaranteed solvable without some better clue about the input string size or repetition count.