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

## 題解

### Brute force

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if needle in haystack:
            length = len(haystack)
            y = len(needle)
            for x in range(length):
                if haystack[x:y] == needle:
                    return x
                y+=1
        else:
            return -1

### Array increase performance

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n,needn = len(haystack),len(needle)
        cur = ccur = 0
        output = 0
        queue = []
        qc = 0
        if n < needn:
            return -1
        while cur < n and ccur < needn:
            if haystack[cur] == needle[0] and cur != output and cur not in queue:
                queue.append(cur)
            if haystack[cur] == needle[ccur]:
                if ccur == 0:
                    output = cur
                ccur += 1
                cur += 1
            else:
                ccur = 0
                if queue and qc < len(queue):
                    cur = queue[qc]
                    qc += 1
                else:
                    cur += 1
            if needle[0:ccur] == needle:
                return output
        return -1

### KMP algorithms

class Solution:
    def strStr(self, haystack: str, pattern: str) -> int:
        # KMP algorithms
        # m = haystack.size()
        # n = pattern.size()
        # Time complexity: O(m+n)
        # Space complexity: O(n)
        def builder() -> List[int]:
            nonlocal pattern
            i,j,n = 1,0,len(pattern)
            build = [0 for i in range(n)]
            while i < n:
                if pattern[i] == pattern[j]:
                    build[i] = j + 1
                    i += 1
                    j += 1
                else:
                    if j != 0:
                        j = build[j-1]
                    else:
                        build[i] = 0
                        i += 1
            return build

        def finder() -> int:
            nonlocal haystack,pattern
            m = len(haystack)
            n = len(pattern)
            i = j = 0
            build = builder()
            while m - j >= n - i: # haystack 要比 pattern 大
                if haystack[j] == pattern[i]:
                    if i == n - 1:
                        return j - i
                    i += 1
                    j += 1
                else:
                    if i != 0:
                        i = build[i-1]
                    else:
                        j += 1
            return -1
        
        return finder()