Repeat problem

[ankurvit]

Hi,

I'm looking to code the following problem in python.
If (for example)
dict={A:0.7,B:0.8,C:0.9,D:2.3,E:0.1,F:2.4} and so on.. (i have a big dictionary of A-Z something like this)
I'm looking to find repeated substring in a string that has a dissimilarity of no longer than 0.5 (between highest and lowest). The length of the repeated substring is provided by the user.

So For example , If my string is
ABCFFEABCFEBCA

my answer would be ABC (with its positions), ABC(with positions in the string) and BCA(with positions in a string) (if the length of the substring provided by the user is 3)
cuz the highest among ABC is C=0.9 and A=0.7 and the difference < 0.5.

A position cannot be repeated in a substring
example
if S=ABCFFFFFF and if i'm looking for repeat length = 2 then
AB and BC will not count as B is a common position in 2 of them.

Any suggestions??

Thanks

[TrustyTony]

I do not know, but I have coded the longest common substring algorithm and mayby you could use similar dynamic programming approach. http://www.daniweb.com/software-development/python/threads/284870/1245223#post1245223

[ankurvit]

This is different from longest common substring problem as the characters are not static.
In my example ABC is similar to BCA as in both the cases highest-lowest will be < 0.5. Longest common substring problem will not detect it.

[TrustyTony]

similar dynamic programming approach.