String Matching

'''
- haystack: string
- needle: string yang dicari
'''
def string_contains(haystack: str, needle: str):
    i = 0
    m = len(needle)
    n = len(haystack)
    contains = False

    # bikin perulangan dari 0 sampai dengan panjang haystack dikurangi panjang needle
    while (i <= n - m) and not contains:
        j = 0
        # perulangan dari 0 sampai dengan panjang needle
        # dan jika karakter haystack ke-i+j sama dengan karakter pada needle ke-j
        # (cocokan satu per satu karakter pada needle dan haystack)
        while (j < m) and (haystack[i+j] == needle[j]):
            j += 1

        # jika j sama dengan panjang needle (berarti semua karakter cocok)
        if j == m:
            contains = True
        else:
            # jika tidak maka i di increment dan ulangi langkah loop ke-2 (pencocokan setiap karakter)
            i += 1

    # jika ketemu balikan i, yaitu indeks needle yang ada pada haystack
    # jika tidak ketemu balikan -1.
    return i if contains else -1

string_contains('NOBODY NOTICED HIM', 'NOT')