Question

Help with Problem Set 3 please. I'm still stuck on the first exercise because I'm doing the iterative program wrong (somehow) and I'm not sure where to start with the recursive one. Code copied in a comment.

Answer 1

def countSubStringMatch(target,key):
'''Searches iteratively for how many key matches can be found.'''
findpos = 0 #counter for what position in target to count from
ans = 0 #variable for number of found key matches in the target
while findpos <= len(target):
if find(target,key,findpos) >= 0:
ans += 1 #increases number of found key matches
findpos += 1 #increases counter
else:
findpos += 1
if ans > 0:
print 'There are',ans,'instances of',key,'in the searched string.'
else:
print 'There are no instances of',key,'in the searched string.'

countSubStringMatch(raw_input('Enter the string to search: '),raw_input('What are you looking for? '))

Answer 2

Ugh, the commented material was messed up there. I hope people can tell what I'm doing there. Please tell me what's wrong with it. That's the iterative program.

Answer 3

I have updated the code somewhat for the iterative program. This is what I have now.

target = raw_input('Enter the string to search: ')
key = raw_input('What are you looking for? ')

def countSubStringMatch(target,key):
'''Searches iteratively for how many key matches can be found.'''
findpos = 0 #counter for what position in target to count from
ans = 0 #variable for number of found key matches in the target
while findpos <= (len(target)-len(key)):
if find(target,key,findpos) >= 0:
ans += 1 #increases number of found key matches
findpos += 1 #increases counter
else:
findpos += 1
if ans > 0:
print 'There are',ans,'instances of',key,'in the searched string.'
else:
print 'There are no instances of',key,'in the searched string.'

countSubStringMatch(target,key)

Answer 4

Basically my problem is that it's displaying more instances than should be possible. If I test 'gatacatctcgagaatagagatcgcgccgata' as my target and search for 'gaga' as the key, it tells me there are 18 instances instead of 2.

Answer 5

You will spot the issue pretty quickly if you look at the string you're evaluating on each iteration, but here's what's going on. say you're looking for 'cat' in string 'cat cat cat' assuming that you get the starting index of the first occurrence, you're incrementing the number of matches, and then incrementing your starting position by 1. on the second iteration you're evaluating 'at cat cat'. the first cat is no longer viable, but the second is found and counted. third iteration tests the string 't cat cat' and again finds the second occurrence from the original string as the first in the new string. Then next cycle does the same, and you'll have found 5 matches before the second instance of cat loses its 'c'. rather than increasing your placeholder by 1, you should increase it to the starting position of the found occurrence plus the length of the substring, so you'll never have duplicate matches for the same find.