Exercise - Super Self Insertion

arithma

Continuing with my set of embarrassing set of exercise titles, I give you "super self insertion".
This was a challenge by my younger brother, after I was enticing him for a little programming appetite.

There is a peculiar function, that given a string, will insert that original string repeatedly into resulting strings.
An example will be particularly effective to explain:
abcd -> ababcdcd -> abaabcdbcdcd
This operation could have been done an arbitrary number of times, without restriction on the position of insertion.

Given an output string, reconstruct the original. As usual, I haven't solved this problem. I don't know if there's a unique solution for every input, so I still abide by returning a list of possible initial strings, and the insertion sequence for each. The above insertion sequence would be: [2, 3], and the original would be abcd obviously.

arithma

This problem is making me absolutely miserable.

xterm

Initial draft, I only tested against arithma's string. (P.S.: Invert the insertion)

Test here but click "Output" to see the output.

def str = "abaabcdbcdcd"

def divs = (2..(int)(str.size()/2)).findAll { str.size() % it == 0 }

divs.each { findOriginal(it,str) }

def findOriginal(window,str){
def len = str.size()
(0..len-window).each {
def token = str[it..it+window-1]
def current = str
def insertion = []
while(current != ""){
if(current.contains(token)){
insertion << current.indexOf(token)
current -= token
} else
break;
if(current == "") println "$insertion : $token"
}
}
}

arithma

Absolutely elegant solution. I couldn't see it not in the most fading way.
Touche sir!

The ball is yours now, post a new exercise!
I'll still trod the tried path I have started, but I know it'll give me more frustration. Trying to solve the problem in reverse, character by character.

ali-koubeissi

I wrote a flawed solution that requires no repeated characters in the repeated strings and the repeated string should be of length 3 or more.

I based my solution on 2 facts:

1 - The first and last character of the input string is the first and last character of the repeated string.
2 - The inner most repeated string is the only unique sequence of characters in the input, which means it will not contain the first/last character when splitted.

namespace SuperSelfInsertion
{
    class Program
    {
        static void Main(string[] args)
        {
            string input = "xyzxyxxyzyzz";

            /* The First/Last letter of the input is always the first/last letter of the repeated string */
            char firstLetter = input[0];
            char LastLetter = input[input.Length - 1];

            /* Chop, chop. */
            var choppedInput = input.Split(firstLetter, LastLetter);

            foreach (var choppedDamnIt in choppedInput)
            {
                /* Empty string, which means a subrepteated string */
                if ( choppedDamnIt.Length <= 0)
                    continue;

                /* If the  chopped string does not contain the first/last character => The inner most repetition => win win. */
                if (!(choppedDamnIt.Contains(firstLetter) &&  choppedDamnIt.Contains(LastLetter)))
                {
                    Console.WriteLine(firstLetter.ToString() + choppedDamnIt + LastLetter.ToString());
                }
            }
        }
    }
}

xterm

I just noticed that my code fails on X¹X²X³...X¹

I'll check it later.

Edit : Solutions are not unique, here's a case : aababaababaaababaa , I started with aba as original yet "ababaa" is also a solution.

Edit #2 : It seems for every window, multiple extraction sequences should be tested, here's why my code fails for aababaababaaababaa with the original string aba :

aababaababaaababaa aba 1
abaababaaababaa aba 0
ababaaababaa aba 0
baaababaa aba 3
baabaa aba 2
baa

Edit #3 : I'm reaching a point where this is virtually unsolvable with O(n^2). The number of insertion sequences is exponential.

Edit #4 : Based on my tests, it seems that (but i can't prove it) for any insertion sequence, the original string should be tested against all shifts of the result. Which means if my window is aba it will be tested against [aba,aab,baa]

Edit #5 : That's a no no, #4 is incorrect it seems. For the string highlighted in #2, baaababaa would get caught as original string :(

Edit #6 : A look ahead block would make this solvable. It feels like building AI for chess...

Edit #7: Solution, sequence trees.

xterm

arithma wroteThis problem is making me absolutely miserable.

I concurrrrrrrrrrrrr!

I'm going to give it one last shot with binary search trees.

arithma

Doesn't this problem feel like this?

xterm

class Node {
int value = -1
def parent
def children = []
String toString() { value }
}

class Tree {
Node root
def data
def token
def leaves = []

void insertion_sequences(){
root = new Node()
build(data,token,root)
find_leaves(root)
def seqs = leaves.collect { route(it) }
seqs.each {
def str = apply_insertion(it)
if(str == data) println "$it"
}
}

def apply_insertion(sequence){
def sb = new StringBuffer(token)
sequence.each {
sb.insert(it.value,token)
}
return sb.toString()
}

def route(leaf){
def rt = []
def current = leaf
while(current.parent != null){
rt << current
current = current.parent
}
return rt
}

def find_leaves(node){
if(node.children.size() == 0) leaves << node
node.children.each { find_leaves(it) }
}

def build(str, token, node){
node.children += insertions(str,token,node)
node.children.each {
def sb = new StringBuffer(str)
sb.replace(it.value,it.value+ token.size(),'')
build(sb.toString(),token,it)
}
}

def insertions(str,token,parent_node){
assert str.indexOf('|') == -1
def data = new StringBuffer(str)
def insertion_points = [] as Set
(data.size() - token.size()).times {
insertion_points << data.indexOf(token)
data.replace(it,it+1,'|')
}
insertion_points.sort().collect { new Node(value: it,parent: parent_node) }
}
}

tree = new Tree(
data: "aabaabaabaaabaaabaaa",
token: "abaa")
tree.insertion_sequences()

xterm

Ok, I updated the previous post with my very last update for this exercise. Although the input of the Tree class requires the original string, that's really not a problem because finding that token is a window algorithm:

"[12]3456789"
"1[23]456789"
"12[34]56789"

and so on until all dividers of data.size()/2 are met.

What I wanted to show is the possible insertion sequences that you get for aabaabaabaaabaaabaaa if the original string is abaa

[3, 3, 3, 1]
[3, 7, 3, 1]
[3, 3, 7, 1]
[3, 7, 7, 1]
[3, 3, 11, 1]
[3, 7, 11, 1]
[3, 3, 1, 7]
[3, 7, 1, 7]
[3, 1, 7, 7]
[1, 7, 7, 7]
[3, 1, 11, 7]
[1, 7, 11, 7]
[3, 3, 1, 11]
[3, 7, 1, 11]
[3, 1, 7, 11]
[1, 7, 7, 11]
[3, 1, 11, 11]
[1, 7, 11, 11]
[3, 3, 1, 15]
[3, 7, 1, 15]
[3, 1, 7, 15]
[1, 7, 7, 15]
[3, 1, 11, 15]
[1, 7, 11, 15]

I failed myself miserably during this exercise, it gave me a headache. I will revisit this during the weekend to refactor, optimize and apply a functional approach.

geek

a simple solution:
0. generate all substrings of the original string
1. for every substring
1.0. remove substring from current string (invert the insertion @xterm)
1.1. iterate until current string becomes empty or the substring can no longer be found

a better one:
0. can be enhanced by considering only substrings that
0.0 having length that divides that of the original string
0.1 contain all the characters of the original string
0.2 agreeing on the first and last character with the original string (@ali.koubeissi)
0.3 for every character, its count in the substring divides its count in the original string, and the quotient is equal for all characters

Timing[
 s = "aaaaaaaaaaaaa";
 
 d = Divisors[StringLength[s]];
 c = Characters[s];
 
 (*\[Rho]=Union@Subsets[c];*)
 (*generate all substrings with length dividing that of the original string*)
 \[Rho] = Union@Flatten[Partition[c, #, 1] & /@ d, 1];
 
 (*substrings containing all the characters of the original string and agreeing on the first and last character*)
 \[Lambda] = Select[\[Rho], Union[#] == Union[c] && #[[1]] == c[[1]] && #[[-1]] == c[[-1]] &];
 (*character count divides that of the original string and the quotient is unique*)
 \[Alpha] = Map[{Map[#[[2]] &, #[[1]]], #[[2]]} &, {Tally[#], #} & /@ \[Lambda]];
 \[Beta] = #[[2]] & /@ Tally[c];
 \[Chi] = StringJoin[#[[2]]] & /@ Select[{\[Beta]/#[[1]], #[[2]]} & /@ \[Alpha], Length@Union@#[[1]] == 1 && IntegerQ@#[[1, 1]] &];
 
 \[Mu] = {s, #, {}} & /@ \[Chi];
 (*no pruning*)
 (*\[Mu]={s,StringJoin[#],{}}&/@\[Rho];*)
 
 \[Nu] = {};
 
 f[l_List] := If[
   (*current string is empty, append substring and indices to the solution*)
   l[[1]] == "", AppendTo[\[Nu], {l[[2]], l[[3]]}],
   (*else, find position(s) of substring*)
   \[Epsilon] = StringPosition[l[[1]], l[[2]]];
   (*apply f to every position*)
   f /@ ({StringReplacePart[l[[1]], "", #], l[[2]], Prepend[l[[3]], #[[1]] - 1]} & /@ \[Epsilon]);
   ];
 (*apply f to substrings*)
 f /@ \[Mu];
 
 (*sort solutions*)
 \[Nu] = SortBy[\[Nu], #[[2]] &];
 
 (*for every solution, check if the sequence of insertions generates the original string*)
 And @@ (#[[1]] == s & /@ (NestWhile[{StringInsert[#[[1]], #[[2]], First@#[[3]] + 1], #[[2]], Rest@#[[3]]} &, {"", #[[1]], #[[2]]}, #[[3]] != {} &] & /@ \[Nu]))
 ]

Print[\[Nu]]

"aaaaa" (0.012168s)
{{aaaaa,{0}},{a,{0,0,0,0,0}},{a,{0,0,0,0,1}},{a,{0,0,0,0,2}},{a,{0,0,0,0,3}},{a,{0,0,0,0,4}},{a,{0,0,0,1,0}},{a,{0,0,0,1,1}},{a,{0,0,0,1,2}},{a,{0,0,0,1,3}},{a,{0,0,0,1,4}},{a,{0,0,0,2,0}},{a,{0,0,0,2,1}},{a,{0,0,0,2,2}},{a,{0,0,0,2,3}},{a,{0,0,0,2,4}},{a,{0,0,0,3,0}},{a,{0,0,0,3,1}},{a,{0,0,0,3,2}},{a,{0,0,0,3,3}},{a,{0,0,0,3,4}},{a,{0,0,1,0,0}},{a,{0,0,1,0,1}},{a,{0,0,1,0,2}},{a,{0,0,1,0,3}},{a,{0,0,1,0,4}},{a,{0,0,1,1,0}},{a,{0,0,1,1,1}},{a,{0,0,1,1,2}},{a,{0,0,1,1,3}},{a,{0,0,1,1,4}},{a,{0,0,1,2,0}},{a,{0,0,1,2,1}},{a,{0,0,1,2,2}},{a,{0,0,1,2,3}},{a,{0,0,1,2,4}},{a,{0,0,1,3,0}},{a,{0,0,1,3,1}},{a,{0,0,1,3,2}},{a,{0,0,1,3,3}},{a,{0,0,1,3,4}},{a,{0,0,2,0,0}},{a,{0,0,2,0,1}},{a,{0,0,2,0,2}},{a,{0,0,2,0,3}},{a,{0,0,2,0,4}},{a,{0,0,2,1,0}},{a,{0,0,2,1,1}},{a,{0,0,2,1,2}},{a,{0,0,2,1,3}},{a,{0,0,2,1,4}},{a,{0,0,2,2,0}},{a,{0,0,2,2,1}},{a,{0,0,2,2,2}},{a,{0,0,2,2,3}},{a,{0,0,2,2,4}},{a,{0,0,2,3,0}},{a,{0,0,2,3,1}},{a,{0,0,2,3,2}},{a,{0,0,2,3,3}},{a,{0,0,2,3,4}},{a,{0,1,0,0,0}},{a,{0,1,0,0,1}},{a,{0,1,0,0,2}},{a,{0,1,0,0,3}},{a,{0,1,0,0,4}},{a,{0,1,0,1,0}},{a,{0,1,0,1,1}},{a,{0,1,0,1,2}},{a,{0,1,0,1,3}},{a,{0,1,0,1,4}},{a,{0,1,0,2,0}},{a,{0,1,0,2,1}},{a,{0,1,0,2,2}},{a,{0,1,0,2,3}},{a,{0,1,0,2,4}},{a,{0,1,0,3,0}},{a,{0,1,0,3,1}},{a,{0,1,0,3,2}},{a,{0,1,0,3,3}},{a,{0,1,0,3,4}},{a,{0,1,1,0,0}},{a,{0,1,1,0,1}},{a,{0,1,1,0,2}},{a,{0,1,1,0,3}},{a,{0,1,1,0,4}},{a,{0,1,1,1,0}},{a,{0,1,1,1,1}},{a,{0,1,1,1,2}},{a,{0,1,1,1,3}},{a,{0,1,1,1,4}},{a,{0,1,1,2,0}},{a,{0,1,1,2,1}},{a,{0,1,1,2,2}},{a,{0,1,1,2,3}},{a,{0,1,1,2,4}},{a,{0,1,1,3,0}},{a,{0,1,1,3,1}},{a,{0,1,1,3,2}},{a,{0,1,1,3,3}},{a,{0,1,1,3,4}},{a,{0,1,2,0,0}},{a,{0,1,2,0,1}},{a,{0,1,2,0,2}},{a,{0,1,2,0,3}},{a,{0,1,2,0,4}},{a,{0,1,2,1,0}},{a,{0,1,2,1,1}},{a,{0,1,2,1,2}},{a,{0,1,2,1,3}},{a,{0,1,2,1,4}},{a,{0,1,2,2,0}},{a,{0,1,2,2,1}},{a,{0,1,2,2,2}},{a,{0,1,2,2,3}},{a,{0,1,2,2,4}},{a,{0,1,2,3,0}},{a,{0,1,2,3,1}},{a,{0,1,2,3,2}},{a,{0,1,2,3,3}},{a,{0,1,2,3,4}}}

"aabaabaabaaabaaabaaa" (0.008s)
{{aabaabaabaaabaaabaaa,{0}},{abaa,{0,1,7,7,7}},{abaa,{0,1,7,7,11}},{abaa,{0,1,7,7,15}},{abaa,{0,1,7,11,7}},{abaa,{0,1,7,11,11}},{abaa,{0,1,7,11,15}},{abaa,{0,3,1,7,7}},{abaa,{0,3,1,7,11}},{abaa,{0,3,1,7,15}},{abaa,{0,3,1,11,7}},{abaa,{0,3,1,11,11}},{abaa,{0,3,1,11,15}},{abaa,{0,3,3,1,7}},{abaa,{0,3,3,1,11}},{abaa,{0,3,3,1,15}},{abaa,{0,3,3,3,1}},{abaa,{0,3,3,7,1}},{abaa,{0,3,3,11,1}},{aaba,{0,3,6,6,6}},{aaba,{0,3,6,6,10}},{aaba,{0,3,6,6,14}},{aaba,{0,3,6,10,6}},{aaba,{0,3,6,10,10}},{aaba,{0,3,6,10,14}},{abaa,{0,3,7,1,7}},{abaa,{0,3,7,1,11}},{abaa,{0,3,7,1,15}},{abaa,{0,3,7,3,1}},{abaa,{0,3,7,7,1}},{abaa,{0,3,7,11,1}}}

"aababaababaaababaa" (0.04399s)
{{aababaababaaababaa,{0}},{ababaa,{0,0,1}},{ababaa,{0,1,6}},{ababaa,{0,1,12}},{aababa,{0,5,5}},{aababa,{0,5,11}},{ababaa,{0,6,1}},{aba,{0,0,0,1,8,14}},{aba,{0,0,0,1,11,8}},{aba,{0,0,0,5,1,14}},{aba,{0,0,0,5,11,1}},{aba,{0,0,0,8,1,8}},{aba,{0,0,0,8,5,1}},{aba,{0,0,1,3,8,14}},{aba,{0,0,1,3,11,8}},{aba,{0,0,1,5,3,14}},{aba,{0,0,1,5,6,14}},{aba,{0,0,1,5,11,3}},{aba,{0,0,1,5,11,6}},{aba,{0,0,1,6,8,14}},{aba,{0,0,1,6,11,8}},{aba,{0,0,1,8,3,8}},{aba,{0,0,1,8,5,3}},{aba,{0,0,1,8,5,6}},{aba,{0,0,1,8,6,8}},{aba,{0,0,1,8,8,12}},{aba,{0,0,1,8,9,8}},{aba,{0,0,1,8,11,12}},{aba,{0,0,1,8,12,14}},{aba,{0,0,1,9,8,14}},{aba,{0,0,1,9,11,8}},{aba,{0,0,2,0,1,14}},{aba,{0,0,2,0,11,1}},{aba,{0,0,2,1,3,14}},{aba,{0,0,2,1,6,14}},{aba,{0,0,2,1,11,3}},{aba,{0,0,2,1,11,6}},{aba,{0,0,2,3,1,14}},{aba,{0,0,2,3,11,1}},{aba,{0,0,2,8,0,1}},{aba,{0,0,2,8,1,3}},{aba,{0,0,2,8,1,6}},{aba,{0,0,2,8,3,1}},{aba,{0,0,3,1,8,14}},{aba,{0,0,3,1,11,8}},{aba,{0,0,3,5,1,14}},{aba,{0,0,3,5,11,1}},{aba,{0,0,3,8,1,8}},{aba,{0,0,3,8,5,1}},{aba,{0,0,5,0,1,8}},{aba,{0,0,5,0,5,1}},{aba,{0,0,5,1,3,8}},{aba,{0,0,5,1,5,3}},{aba,{0,0,5,1,5,6}},{aba,{0,0,5,1,6,8}},{aba,{0,0,5,1,8,12}},{aba,{0,0,5,1,9,8}},{aba,{0,0,5,1,11,12}},{aba,{0,0,5,1,12,14}},{aba,{0,0,5,2,0,1}},{aba,{0,0,5,2,1,3}},{aba,{0,0,5,2,1,6}},{aba,{0,0,5,2,3,1}},{aba,{0,0,5,3,1,8}},{aba,{0,0,5,3,5,1}},{aba,{0,0,5,5,1,12}},{aba,{0,0,5,5,9,1}},{aba,{0,0,5,6,1,8}},{aba,{0,0,5,6,5,1}},{aba,{0,0,5,8,1,12}},{aba,{0,0,5,8,9,1}},{aba,{0,0,5,9,1,14}},{aba,{0,0,5,9,11,1}},{aba,{0,0,6,1,8,14}},{aba,{0,0,6,1,11,8}},{aba,{0,0,6,5,1,14}},{aba,{0,0,6,5,11,1}},{aba,{0,0,6,8,1,8}},{aba,{0,0,6,8,5,1}},{aba,{0,1,3,3,8,14}},{aba,{0,1,3,3,11,8}},{aba,{0,1,3,5,3,14}},{aba,{0,1,3,5,6,14}},{aba,{0,1,3,5,11,3}},{aba,{0,1,3,5,11,6}},{aba,{0,1,3,6,8,14}},{aba,{0,1,3,6,11,8}},{aba,{0,1,3,8,3,8}},{aba,{0,1,3,8,5,3}},{aba,{0,1,3,8,5,6}},{aba,{0,1,3,8,6,8}},{aba,{0,1,3,8,8,12}},{aba,{0,1,3,8,9,8}},{aba,{0,1,3,8,11,12}},{aba,{0,1,3,8,12,14}},{aba,{0,1,3,9,8,14}},{aba,{0,1,3,9,11,8}},{aba,{0,1,5,3,3,8}},{aba,{0,1,5,3,5,3}},{aba,{0,1,5,3,5,6}},{aba,{0,1,5,3,6,8}},{aba,{0,1,5,3,8,12}},{aba,{0,1,5,3,9,8}},{aba,{0,1,5,3,11,12}},{aba,{0,1,5,3,12,14}},{aba,{0,1,5,5,3,12}},{aba,{0,1,5,5,6,12}},{aba,{0,1,5,5,9,3}},{aba,{0,1,5,5,9,6}},{aba,{0,1,5,6,3,8}},{aba,{0,1,5,6,5,3}},{aba,{0,1,5,6,5,6}},{aba,{0,1,5,6,6,8}},{aba,{0,1,5,6,8,12}},{aba,{0,1,5,6,9,8}},{aba,{0,1,5,6,11,12}},{aba,{0,1,5,6,12,14}},{aba,{0,1,5,8,3,12}},{aba,{0,1,5,8,6,12}},{aba,{0,1,5,8,9,3}},{aba,{0,1,5,8,9,6}},{aba,{0,1,5,9,3,14}},{aba,{0,1,5,9,6,14}},{aba,{0,1,5,9,11,3}},{aba,{0,1,5,9,11,6}},{aba,{0,1,6,3,8,14}},{aba,{0,1,6,3,11,8}},{aba,{0,1,6,5,3,14}},{aba,{0,1,6,5,6,14}},{aba,{0,1,6,5,11,3}},{aba,{0,1,6,5,11,6}},{aba,{0,1,6,6,8,14}},{aba,{0,1,6,6,11,8}},{aba,{0,1,6,8,3,8}},{aba,{0,1,6,8,5,3}},{aba,{0,1,6,8,5,6}},{aba,{0,1,6,8,6,8}},{aba,{0,1,6,8,8,12}},{aba,{0,1,6,8,9,8}},{aba,{0,1,6,8,11,12}},{aba,{0,1,6,8,12,14}},{aba,{0,1,6,9,8,14}},{aba,{0,1,6,9,11,8}},{aba,{0,2,0,0,1,8}},{aba,{0,2,0,0,5,1}},{aba,{0,2,0,1,3,8}},{aba,{0,2,0,1,5,3}},{aba,{0,2,0,1,5,6}},{aba,{0,2,0,1,6,8}},{aba,{0,2,0,1,8,12}},{aba,{0,2,0,1,9,8}},{aba,{0,2,0,1,11,12}},{aba,{0,2,0,1,12,14}},{aba,{0,2,0,2,0,1}},{aba,{0,2,0,2,1,3}},{aba,{0,2,0,2,1,6}},{aba,{0,2,0,2,3,1}},{aba,{0,2,0,3,1,8}},{aba,{0,2,0,3,5,1}},{aba,{0,2,0,5,1,12}},{aba,{0,2,0,5,9,1}},{aba,{0,2,0,6,1,8}},{aba,{0,2,0,6,5,1}},{aba,{0,2,0,8,1,12}},{aba,{0,2,0,8,9,1}},{aba,{0,2,0,9,1,14}},{aba,{0,2,0,9,11,1}},{aba,{0,2,1,3,3,8}},{aba,{0,2,1,3,5,3}},{aba,{0,2,1,3,5,6}},{aba,{0,2,1,3,6,8}},{aba,{0,2,1,3,8,12}},{aba,{0,2,1,3,9,8}},{aba,{0,2,1,3,11,12}},{aba,{0,2,1,3,12,14}},{aba,{0,2,1,5,3,12}},{aba,{0,2,1,5,6,12}},{aba,{0,2,1,5,9,3}},{aba,{0,2,1,5,9,6}},{aba,{0,2,1,6,3,8}},{aba,{0,2,1,6,5,3}},{aba,{0,2,1,6,5,6}},{aba,{0,2,1,6,6,8}},{aba,{0,2,1,6,8,12}},{aba,{0,2,1,6,9,8}},{aba,{0,2,1,6,11,12}},{aba,{0,2,1,6,12,14}},{aba,{0,2,1,8,3,12}},{aba,{0,2,1,8,6,12}},{aba,{0,2,1,8,9,3}},{aba,{0,2,1,8,9,6}},{aba,{0,2,1,9,3,14}},{aba,{0,2,1,9,6,14}},{aba,{0,2,1,9,11,3}},{aba,{0,2,1,9,11,6}},{aba,{0,2,2,0,1,12}},{aba,{0,2,2,0,9,1}},{aba,{0,2,2,1,3,12}},{aba,{0,2,2,1,6,12}},{aba,{0,2,2,1,9,3}},{aba,{0,2,2,1,9,6}},{aba,{0,2,2,3,1,12}},{aba,{0,2,2,3,9,1}},{aba,{0,2,2,6,0,1}},{aba,{0,2,2,6,1,3}},{aba,{0,2,2,6,1,6}},{aba,{0,2,2,6,3,1}},{aba,{0,2,3,0,1,8}},{aba,{0,2,3,0,5,1}},{aba,{0,2,3,1,3,8}},{aba,{0,2,3,1,5,3}},{aba,{0,2,3,1,5,6}},{aba,{0,2,3,1,6,8}},{aba,{0,2,3,1,8,12}},{aba,{0,2,3,1,9,8}},{aba,{0,2,3,1,11,12}},{aba,{0,2,3,1,12,14}},{aba,{0,2,3,2,0,1}},{aba,{0,2,3,2,1,3}},{aba,{0,2,3,2,1,6}},{aba,{0,2,3,2,3,1}},{aba,{0,2,3,3,1,8}},{aba,{0,2,3,3,5,1}},{aba,{0,2,3,5,1,12}},{aba,{0,2,3,5,9,1}},{aba,{0,2,3,6,1,8}},{aba,{0,2,3,6,5,1}},{aba,{0,2,3,8,1,12}},{aba,{0,2,3,8,9,1}},{aba,{0,2,3,9,1,14}},{aba,{0,2,3,9,11,1}},{aba,{0,2,5,0,1,12}},{aba,{0,2,5,0,9,1}},{aba,{0,2,5,1,3,12}},{aba,{0,2,5,1,6,12}},{aba,{0,2,5,1,9,3}},{aba,{0,2,5,1,9,6}},{aba,{0,2,5,3,1,12}},{aba,{0,2,5,3,9,1}},{aba,{0,2,5,6,0,1}},{aba,{0,2,5,6,1,3}},{aba,{0,2,5,6,1,6}},{aba,{0,2,5,6,3,1}},{aba,{0,2,6,0,1,14}},{aba,{0,2,6,0,11,1}},{aba,{0,2,6,1,3,14}},{aba,{0,2,6,1,6,14}},{aba,{0,2,6,1,11,3}},{aba,{0,2,6,1,11,6}},{aba,{0,2,6,3,1,14}},{aba,{0,2,6,3,11,1}},{aba,{0,2,6,8,0,1}},{aba,{0,2,6,8,1,3}},{aba,{0,2,6,8,1,6}},{aba,{0,2,6,8,3,1}},{aba,{0,3,0,1,8,14}},{aba,{0,3,0,1,11,8}},{aba,{0,3,0,5,1,14}},{aba,{0,3,0,5,11,1}},{aba,{0,3,0,8,1,8}},{aba,{0,3,0,8,5,1}},{aba,{0,3,1,3,8,14}},{aba,{0,3,1,3,11,8}},{aba,{0,3,1,5,3,14}},{aba,{0,3,1,5,6,14}},{aba,{0,3,1,5,11,3}},{aba,{0,3,1,5,11,6}},{aba,{0,3,1,6,8,14}},{aba,{0,3,1,6,11,8}},{aba,{0,3,1,8,3,8}},{aba,{0,3,1,8,5,3}},{aba,{0,3,1,8,5,6}},{aba,{0,3,1,8,6,8}},{aba,{0,3,1,8,8,12}},{aba,{0,3,1,8,9,8}},{aba,{0,3,1,8,11,12}},{aba,{0,3,1,8,12,14}},{aba,{0,3,1,9,8,14}},{aba,{0,3,1,9,11,8}},{aba,{0,3,2,0,1,14}},{aba,{0,3,2,0,11,1}},{aba,{0,3,2,1,3,14}},{aba,{0,3,2,1,6,14}},{aba,{0,3,2,1,11,3}},{aba,{0,3,2,1,11,6}},{aba,{0,3,2,3,1,14}},{aba,{0,3,2,3,11,1}},{aba,{0,3,2,8,0,1}},{aba,{0,3,2,8,1,3}},{aba,{0,3,2,8,1,6}},{aba,{0,3,2,8,3,1}},{aba,{0,3,3,1,8,14}},{aba,{0,3,3,1,11,8}},{aba,{0,3,3,5,1,14}},{aba,{0,3,3,5,11,1}},{aba,{0,3,3,8,1,8}},{aba,{0,3,3,8,5,1}},{aba,{0,3,5,0,1,8}},{aba,{0,3,5,0,5,1}},{aba,{0,3,5,1,3,8}},{aba,{0,3,5,1,5,3}},{aba,{0,3,5,1,5,6}},{aba,{0,3,5,1,6,8}},{aba,{0,3,5,1,8,12}},{aba,{0,3,5,1,9,8}},{aba,{0,3,5,1,11,12}},{aba,{0,3,5,1,12,14}},{aba,{0,3,5,2,0,1}},{aba,{0,3,5,2,1,3}},{aba,{0,3,5,2,1,6}},{aba,{0,3,5,2,3,1}},{aba,{0,3,5,3,1,8}},{aba,{0,3,5,3,5,1}},{aba,{0,3,5,5,1,12}},{aba,{0,3,5,5,9,1}},{aba,{0,3,5,6,1,8}},{aba,{0,3,5,6,5,1}},{aba,{0,3,5,8,1,12}},{aba,{0,3,5,8,9,1}},{aba,{0,3,5,9,1,14}},{aba,{0,3,5,9,11,1}},{aba,{0,3,6,1,8,14}},{aba,{0,3,6,1,11,8}},{aba,{0,3,6,5,1,14}},{aba,{0,3,6,5,11,1}},{aba,{0,3,6,8,1,8}},{aba,{0,3,6,8,5,1}}}

"abaabcdbcdcd" (0.000881s)
{{abaabcdbcdcd,{0}},{abcd,{0,2,3}}}

this becomes intractable as the length of the string increases; the search space grows exponentially.
probably there's a much better way involving automata and string matching.

xterm

Very nice Geek, you seem to have more insertion sequences than I do, ill cnjeck what went wrong.

xterm

Hmmmm, something may not be right in your solution. For the string aabaabaabaaabaaabaaa, 0-3-6-6-14 does not yield the correct string. (I took one of the sequences that does not exist in my result). In fact, double check all 6/4/10 insertion points.

Edit : Oops! I didn't notice that the token was aaba. Yup we're getting sme results.