Boyer-Moore.swift

extension String {
	func distanceIn(cView: String.CharacterView, toMatchingCharacter match: Character) -> Int {
		var count = 0
		
		for c in cView.reverse() {
			if c == match {
				return count
			} else {
				count++
			}
		}
		
		return count
	}
	
	func badCharacterRule(pattern: String.CharacterView) -> Int {
		let substring = self.characters.prefix(pattern.count)
		
		var offset = 0
		for (sub, pat) in zip(substring.reverse(), pattern.reverse()) {
			if sub == pat {
				offset++
			} else {
				let endIndex = substring.endIndex.advancedBy(-offset)
				return offset + distanceIn(pattern[substring.startIndex..<endIndex], toMatchingCharacter: sub)
			}
		}
		
		return offset
	}
	
	func boyerMoore(pattern: String) -> Int {
		var offset = 0
		
		while offset + pattern.characters.count < self.characters.count {
			let startIndex = self.characters.startIndex.advancedBy(offset)
			let endIndex = startIndex.advancedBy(pattern.characters.count)
			
			let badCharacterOffset = self[startIndex..<endIndex].badCharacterRule(pattern.characters)
			
			if badCharacterOffset == pattern.characters.count {
				return offset
			} else {
				offset += badCharacterOffset
			}
		}
		
		return -1
	}
}

let _ =       "12345678"
let pattern = "CCTTTTGC"
let str =     "GCTTCTGCTACCTTTTGCGCGCGCCTTTGCA"

print(str.boyerMoore(pattern) == 10)