def Index(s1,s2,pos = 0):
    """ BF算法 """
    i = pos
    j = 0
    while(i < len(s1) and j < len(s2)):
        if(s1[i] ==  s2[j]):
            i += 1
            j += 1
        else:
            i = i - j + 1
            j = 0
    if(j >= len(s2)):
        return i - len(s2)
    else:
        return 0

if __name__ == "__main__":
    s1 = "ababcabcacbab"
    s2 = "abcac"
    print(Index(s1,s2))

# KMP算法

def Index_KMP(s1,s2,pos=0):
    next = get_next(s2)
    i = pos
    j = 0
    while(i < len(s1) and j < len(s2)):
        if(j == -1 or s1[i] == s2[j]):
            i += 1
            j += 1
        else:
            j = next[j]

    if(j >= len(s2)):
        return i - len(s2)
    else:
        return 0

def get_next(s2):
    i = 0
    next = [-1]
    j = -1
    while(i <len(s2)-1):
        if(j == -1 or s2[i] == s2[j]):
            i += 1
            j += 1
            next.append(j)
        else:
            j = next[j]
    return next

if __name__ == "__main__":
    s1 = "acabaabaabcacaabc"
    s2 = "abaabcac"
    print(Index_KMP(s1,s2))