Leetcode 28. Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

The brute force way is O(len(haystack) * len(needle)) which is O(n*m)

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if haystack is None or needle is None:
            return -1

        for i in range(0, len(haystack) - len(needle) + 1):
            for j in range(0, len(needle)):
                if haystack[i+j] != needle[j]:
                    break

                if j + 1 == len(needle):
                    return i

        return -1

Better way is doing this by KMP, which can be O(n+m)