Knuth-Morris-Pratt Search Algorithm

kmp_search.cdc

/// Computes the longest proper prefix which is suffix (LPS) array
///
access(all) fun computeLPSArray(w: String, m: Int): [Int] {
    var len: Int = 0
    let lps: [Int] = [0]
    var i: Int = 1

    while i < m {
        if w.length > i && w[i] == w[len] {
            len = len + 1
            lps.insert(at: i, len)
            i = i + 1
        } else {
            if len != 0 {
                len = lps[len - 1]
            } else {
                lps.insert(at: i, 0)
                i = i + 1
            }
        }
    }
    log(lps)
    return lps
}

/// Executes KMP search
access(all) fun kmpSearch(s: String, w: String): [Int] {
    var m: Int = w.length
    var n: Int = s.length

    let lps: [Int] = computeLPSArray(w: w, m: m)
    var j: Int = 0

    var i = 0
    let matches: [Int] = []
    while (n - i) >= (m - j) {
        if w[j] == s[i] {
            i = i + 1
            j = j + 1
        }

        if j == m {
            matches.append(i - j)
            j = lps[j - 1]
        } else if i < n && w[j] != s[i] {
            if j != 0 {
                j = lps[j - 1]
            } else {
                i = i + 1
            }
        }
    }

    return matches
}

/// Executes Knuth-Morris-Pratt algorithm for a given substring in a provided string
/// The returned Int array contains the indices where the substring occurs
///
/// @param s: The string in which to search for the word (substring)
/// @param w: The word AKA substring to locate in the given string
///
/// @return An array of indices where the word occurs in the string
///
access(all) fun main(s: String, w: String): [Int] {
    return kmpSearch(s: s, w: w)
}