MIT 6.00 Problem Set 3 - Problem 1 Answer

Emerald Hummingbird, but which kind?, Costa Rica

Python Code Answer:

from string import *

def countSubStringMatch(target, key):
    index = 0
    count = 0

    while True:
        index = find(target, key, index)
        if index == -1:
            break
        index += len(key) 
        print "index %d" % (index)
        count += 1

    return count


def countSubStringMatchRecursive(target, key):
    index = 0
    count = 0

    index = find(target, key, index)

    if index != -1:
        count += 1
        index += len(key)
        print "index %d" % (index) 
        print "target[index:]: %s" % (target[index:])
        count += countSubStringMatchRecursive(target[index:], key)

    return count
    


print countSubStringMatch("XXXXXbeepXXXXbeepXXXbeepXXbeepXbeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatch("beepbeepbeepbeepbeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatch("beepeepbeepbeebeepeepbeepbeebeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatch("beep", "beep")
print "---------------------------------------------"
print countSubStringMatch("", "beep")
print "---------------------------------------------"

print countSubStringMatchRecursive("XXXXXbeepXXXXbeepXXXbeepXXbeepXbeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatchRecursive("beepbeepbeepbeepbeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatchRecursive("beepeepbeepbeebeepeepbeepbeebeepbeep", "beep")
print "---------------------------------------------"
print countSubStringMatchRecursive("beep", "beep")
print "---------------------------------------------"
print countSubStringMatchRecursive("", "beep")
print "---------------------------------------------"

Output:

index 9
index 17
index 24
index 30
index 35
index 39
6
---------------------------------------------
index 4
index 8
index 12
index 16
index 20
index 24
6
---------------------------------------------
index 4
index 11
index 18
index 25
index 32
index 36
6
---------------------------------------------
index 4
1
---------------------------------------------
0
---------------------------------------------
index 9
target[index:]: XXXXbeepXXXbeepXXbeepXbeepbeep
index 8
target[index:]: XXXbeepXXbeepXbeepbeep
index 7
target[index:]: XXbeepXbeepbeep
index 6
target[index:]: Xbeepbeep
index 5
target[index:]: beep
index 4
target[index:]:
6
---------------------------------------------
index 4
target[index:]: beepbeepbeepbeepbeep
index 4
target[index:]: beepbeepbeepbeep
index 4
target[index:]: beepbeepbeep
index 4
target[index:]: beepbeep
index 4
target[index:]: beep
index 4
target[index:]:
6
---------------------------------------------
index 4
target[index:]: eepbeepbeebeepeepbeepbeebeepbeep
index 7
target[index:]: beebeepeepbeepbeebeepbeep
index 7
target[index:]: eepbeepbeebeepbeep
index 7
target[index:]: beebeepbeep
index 7
target[index:]: beep
index 4
target[index:]:
6
---------------------------------------------
index 4
target[index:]:
1
---------------------------------------------
0
---------------------------------------------

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-00-introduction-to-computer-science-and-programming-fall-2008/assignments/pset3.pdf