Skip to content

Instantly share code, notes, and snippets.

@dawand
Created June 24, 2017 12:37
Show Gist options
  • Save dawand/2f614774bbeeadb8e61c2601808ba22d to your computer and use it in GitHub Desktop.
Save dawand/2f614774bbeeadb8e61c2601808ba22d to your computer and use it in GitHub Desktop.
Word Count - Knuth-Morris Pratt algorithm
class KMP {
// used for KMP, Build pi function of prefixes
class func build_pi(_ str: String) -> [Int] {
let n = str.characters.count
var pi = Array(repeating: 0, count: n + 1)
var k:Int = -1
pi[0] = -1
for i in 0..<n {
while (k >= 0 && (str[str.characters.index(str.startIndex, offsetBy: k)] != str[str.characters.index(str.startIndex, offsetBy: i)])) {
k = pi[k]
}
k+=1
pi[i + 1] = k
}
return pi
}
// Knuth-Morris Pratt algorithm
class func search(text:String, pattern: String) -> [Int] {
// Convert to Character array to index in O(1)
var patt = Array(pattern.characters)
var S = Array(text.characters)
var matches = [Int]()
let n = text.characters.count
let m = pattern.characters.count
var k = 0
var pi = build_pi(pattern)
for i in 0..<n {
while (k >= 0 && (k == m || patt[k] != S[i])) {
k = pi[k]
}
k += 1
if (k == m) {
matches.append(i - m + 1)
}
}
return matches
}
}
let words = KMP.search(text:"hello, this is a new text and a new line", pattern: "new")
print(words) // [17, 32]
print(words.count) // 2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment