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

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


Re: Repeat problem 80 80

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.

Re: Repeat problem 80 80

similar dynamic programming approach.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of 1.18 million developers, IT pros, digital marketers, and technology enthusiasts learning and sharing knowledge.