G. Polya, "How to Solve It"....Subsequence part II

I'm running out of time on this one so reluctantly I'm posting my results so far.

Unfortunately the last test case I wrote is failing. After taking a little break and revisiting the problem and being unable to get the last test case to work I'm almost certain this algorithm is very wrong and I would most likely start from scratch on this one.

But as the process of problem solving goes this is where I'm at at the moment, and the moment is slowly running out.

def sub_seq(s, sub):

'''Return the number of times the string sub if found (not necisarly

adjacently) in the string s.

'''

return _sub_seq(s, sub)

def _sub_seq(s, sub, index=0, count=0):

'''Helper for Seb_seq

'''

if sub:

index = s.find(sub[0])

if sub[0] != sub[-1]:

count += 1

return _sub_seq(s,sub[1:], index, count)

else:

while index <>

count += 1

index = s.find(sub[0], index + 1)

return count - 1

else:

return

if __name__=='__main__':

# a substring with the first character in the 0th index

s = '12'

sub = '12'

assert sub_seq(s, sub) == 1

s = '123232'

sub = '12'

assert sub_seq(s, sub) == 3

# a substring with the first character in a random index

s = '8888188882'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 1

# a substring with the first character in a random index

s = '8888188882888882'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 2

# This is Failing

# a substring with the first indices repeating

s = '1212'

sub = '12'

sub_seq(s, sub)

assert sub_seq(s, sub) == 3, 'got %d' %sub_seq(s, sub)