Issue Description:

The following piece of code:

import Foundation

let repeating = "\"."
let original = String(repeating: repeating, count: 1000000)

let start = Date()
_ = original.replacingOccurrences(of: "\"", with: "")
print("took: \(Date().timeIntervalSinceReferenceDate - start.timeIntervalSinceReferenceDate)")

takes over 20s on Linux (4.1 release, Ubuntu 14.04), in comparison to Darwin version, which takes 0.1s.

The cause is O(n^2) algorithm, or more precisely O(m*n), where m is number of matches, n is the length of the string, used here:

If we built up a new string afresh, appending segments that don't match, we'd have O(n) algorithm.