关于自研字符串搜索算法的平均及最坏时间复杂度的咨询

我自己写了一个字符串搜索算法，用来返回needle在haystack中第一次出现的索引，如果不存在就返回-1。这个算法在LeetCode上通过了测试，测试用例里haystack和needle的长度范围是1到10^4。看到有人说O(nm)*的解法根本过不了，所以我觉得我的算法平均时间复杂度应该比这个要好，但我拿不准——主要是那个主while循环的时间复杂度不太好分析。

我的代码如下：

def stringSearch(haystack, needle):
    s = []
    
    if len(needle) == 1:
        for i,n in enumerate(haystack):
            if n == needle:
                return i
        return -1

    for i,n in enumerate(haystack):
        if n == needle[0] and (len(haystack) - i) >= len(needle):
            s.append(i)
    
    new = []
    for i in s:
        if i + 1 < len(haystack) and haystack[i + 1] == needle[1]:
            new.append((i, i + 1, 2))
    if new and len(needle) == 2:
        return new[0][0]

    while 1:
        temp = []
        for first, start, check in new:
            if haystack[start + 1] == needle[check]:
                temp.append((first, start + 1, check + 1))
                if check + 1 >= len(needle):
                    return first
        if not temp:
            return -1
        new = temp
stringSearch("", "")

我能确定的是最坏情况出现在haystack是大量重复的模式，而needle也匹配这个模式的时候，比如haystack是"hahahahahahahah"、needle是"haha"，或者haystack是"aaaaaaaaaaaaaaaaaaaaa"、needle是"aa"这种场景。

备注：内容来源于stack exchange，提问作者juicy