"Understanding how DNA transmits all it knows about cancer, physics, dreaming and love will keep man searching for some time." David R. Brower

The subsequence teaser question that was given out in class on friday kept me thinking for a while about it. I guess it was the fact that the natural solution was one thats implementation was extremely long that kept me thinking. I guess I never really thought about the fact that there are problems that need solving all around us that may be hard to solve just because of their size.

Any way I thought about a possible solution and I don't even know if I'm on the right track or not nut I figured I would jot down my thoughts and maybe latter try to code it up and see if im on the right track.

Here it is.

Scan the list once. While doing so create a dictionary with the items of the list as keys and there index placements in the list as values. in addition to that create a binary search tree from the list in order to cut down search time when retrieving a certain element from a list.

given a a case that the main string was 'xyxayxya' and you were looking for the number of occurrences of 'xya' instead of looking at the string you can refer to the dictionary that would look like this

{'a': [3, 6], 'x': [0, 2, 5], 'y': [1, 4]}

then for every character of the sub string 'xya' you check recursively how many times the next character happens at an index that is strictly larger.

looking at x[0] would return y[1] would return a[3, 6] would return y[4] would return a[6]

looking at x[2] would return y[4] would return a[6]

looking at x[5] would return nothing because there is no y at a bigger index.

I'll try to code this up and see where it goes.

Thanks for reading