KMP

implement by Swift

class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        if needle.count == 0 { return 0 }
        
        var prefix = buildPrefixArray(needle)
        var i = 0, j = 0
        let haystack = Array(haystack), needle = Array(needle)
        while i < haystack.count {
            if haystack[i] == needle[j] {
                i += 1
                j += 1
            } else {
                j = prefix[j]
                if j == -1 {
                    j = 0
                    i += 1
                }
            }
            if j == needle.count { return i - needle.count }
        }
        return -1
    }

    func buildPrefixArray(_ s: String) -> [Int] {
        let n = s.count
        var prefix = Array(repeating: 0, count: n)
        
        var len = 0, i = 1
        let s = Array(s)
        while i < n {
            if s[len] == s[i] {
                len += 1
                prefix[i] = len
                i += 1
            } else {
                if len == 0 {
                    prefix[i] = 0
                    i += 1
                } else {
                    len = prefix[len-1]
                }
            }
        }

        return [-1] + prefix[0..<n-1]
    }
}