Question

For PS3 problem 3...is the formula provided wrong? (n+m=1 = k) As far as I can tell I implemented it properly, however it doesn't seem to catch indices when the second substring is an empty one.

My code is here: http://pastebin.com/3veD3Qc7

So for example: for the substring 'bab' in target string 'aababaa', you would split the substring into 'ba' and '' (an empty string). Obviously the places in the target string where this substitution appear are at index 2 and 4. But using this formula, the result will only be 2.

Answer 1

This is because:

The first tuple (for 'ba') will be 2, 4.
The second tuple (for '', the empty string) will always be all indices: 0, 1, 2, 3, 4, 5, 6.
The length of 'ba' is 2.

Index 4 is what isn't appearing, because:

4+2+1=7

Obviously, there's no index 7 when the length of the target string is 7, and as a result, index 4 is not considered an answer.

So, is the formula in the problem set actually incorrect, or am I doing something wrong with my code?

Answer 2

Note: I'm not necessarily asking how to fix my code and get it working, I think I know how to do that. What I really want to know is if the problem is me and my code, or if the formula itself is wrong.

Answer 3

Here's what my code says:
>>> subStringMatchExact('aababaa', '')
(0, 1, 2, 3, 4, 5, 6, 7)
Since the empty string will match before the first 'a' it will match after the last 'a'.

>>> import string
>>> string.find("aababaa", "", 6)
6
>>> string.find("aababaa", "", 7)
7
>>> string.find("aababaa", "", 8) # Why doesn't this raise an IndexError?!
-1
>>> "aababaa"[7]
IndexError: string index out of range
>>> "aababaa"[7:]
'' (empty string)

Remember, for string slicing and searching, think of the indices as *between* the characters.

So, I would say your solution to problem 2 was not exactly right. Unfortunately the test cases they gave us didn't test this case. But I didn't write a test for this case, either, so don't feel bad about missing it. ;)

BTW, I didn't look at your code at all. I just looked at the test results you posted. This is an example of an excellently-asked question. Very different from most of the question askers in the math forum. Thanks.