Finding the longest (or all) intersection(s) in word level of two strings in Swift 3

Assume two strings:

• String 1: "Once upon a time there was a beautiful princess named Snow white..."
• String 2: "Of course it was a time for a beautiful princess to become one..."

What is the best way to find the longest "intersection" (or all possible intersections) in word level of two strings in Swift? In the previous case it would be: "a beautiful princess".

Here is a basic approach to get a word level intersection of two strings. It's based on a matrix that contains all ordered matches of the strings:

extension String {
  
  func intersection(_ text: String) -> [String] {
    var set = Set<[Substring]>()
    
    let first = split(separator: " ")
    let second = text.split(separator: " ")
    var matrix = [[Substring?]](repeating: [Substring?](repeating: nil, count: second.count), count: first.count)
    
    func prefix(_ i: Int, _ j: Int, _ suffix: [Substring]) -> [Substring] {
      guard i > 0 && j > 0, let sub = matrix[i - 1][j - 1] else {
        return suffix
      }
      return prefix(i - 1, j - 1, [sub] + suffix)
    }

    for i in 0..<first.count {
      let sub = first[i]
      for j in 0..<second.count {
        guard sub == second[j] else {
          continue
        }
        
        matrix[i][j] = sub
        let items = prefix(i, j, [sub])
        
        if items.count > 1 {
          set.remove(Array(items[0..<items.count-1]))
        }
        
        set.insert(items)
      }
    }
    
    return set.map { $0.joined(separator: " ") }
  }
}

With your string it produces the following result:

let text1 = "Once upon a time there was a beautiful princess named Snow white..."
let text2 = "Of course it was a time for a beautiful princess to become one..."

let set = text1.intersection(text2)
print(set) // ["a time", "was a", "a beautiful princess"]