Q:

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-click 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)?

A:

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.

