判断字符串中是否包含子串

# -*- coding: utf-8 -*-
# 难点在于判断到不匹配后，如何选择下一轮比较的起始位置，本次使用Sunnday算法，只介绍匹配失败情况后如和更新下一轮

# 匹配失败情况1：若判断abcfjabcde 中是否有abcd，则会在下处对比失败
# abc f jabcde
# abc d
# 此时判断下一位，即j，是否出现在子串abcd中，如果不存在，则需将i置为j后的a的位置继续进行对比(i = (i + len(sub_str) - j) + 1)，即
# abcfj a bcde
#       a bcd


# 匹配失败情况2：若判断abcabcde中是否有abcd，则会在下处对比时失败
# abc a bcde
# abc d
# 此时判断下一位，即d，是否出现在子串abcd中，如果存在，则需将母串中的b与子串中倒数第一个b对齐(i = (i + len(sub_str) - j) - index)，即：
# abca b cde
#    a b cd

# (i + len(sub_str) - j)是个重要的位置，始终指向子串外的第一个字符在母串中的位置。
def Sunnday(str, sub_str):
    i = 0
    j = 0
    while i <= len(str)-len(sub_str):
        while j < len(sub_str):
            if str[i] == sub_str[j]:
                i += 1
                j += 1

                if j == len(sub_str):
                    return True
            else:
                index = isContain(sub_str, str[i+len(sub_str)-j])
                # 匹配失败情况1
                if index == -1:
                    i = (i + len(sub_str) - j) + 1
                    j = 0
                # 匹配失败情况2
                else:
                    i = (i + len(sub_str) - j) - index
                    j = 0

                break
    return False


# 返回ch在str中的下标（0开始）
def isContain(str, ch):
    i = len(str)-1
    while i >= 0:
        if str[i] == ch:
            return i
        i = i-1

    return -1