Solution to LeetCode problem, String Matching in an Array. https://leetcode.com/problems/string-matching-in-an-array/

String_Matching_in_an_Array.swift

class Solution {
    func stringMatching(_ words: [String]) -> [String] {
        
        var matched = Set<String>()
        for idx in 0..<words.count {
            let pattern = words[idx]
            
            for j in 0..<words.count {
                if j == idx { continue }
                
                if contains(words[j], pattern) {
                    matched.insert(pattern)
                }
            }
        }
        
        return Array(matched)
    }
    
    private func buildKMP(_ pattern: String) -> [Int] {
        let strs = Array(pattern).map { String($0) }
        var kmp = Array(repeating: 0, count: strs.count)
        
        var i = 1
        var j = 0
        while i < strs.count {
            if strs[i] == strs[j] {
                kmp[i] = j + 1
                i += 1
                j += 1
            }
            else {
                if j != 0 {
                    j = kmp[j - 1]
                }
                else {
                    i += 1
                }
            }
        }
        
        return kmp
    }
    
    private func contains(_ source_: String, _ pattern_: String) -> Bool {
        if pattern_.count > source_.count { return false }
        
        let kmp = buildKMP(pattern_)
        let pattern = Array(pattern_).map {String($0)}
        let source = Array(source_).map {String($0)}
        
        var i = 0
        var j = 0
        while i < source.count {
            if source[i] == pattern[j] {
                i += 1
                j += 1
            }
            
            if j == pattern.count {
                return true
            }
            else if i < source.count && source[i] != pattern[j] {
                if j != 0 {
                    j = kmp[j - 1]
                }
                else {
                    i += 1
                }
            }
        }
        
        return false
    }
}