谈到最公共子串，你稍微有点数学常识，就一定可以自己写出这么一个递推方程出来。
递推方程
那么既然有了这么一个递推方程，我想，你也很容易就写出下面这么一段代码来求解最长公共子串的长度的代码咯··
import UIKit
func findLCS(first: String, second: String) -> Int {
if first.characters.count == 0 || second.characters.count == 0 {
return 0
}
if first.characters.last == second.characters.last {
return findLCS(
first.substringToIndex(first.endIndex.predecessor()),
second: second.substringToIndex(second.endIndex.predecessor())) + 1
} else {
return max(
findLCS(first.substringToIndex(first.endIndex.predecessor()), second: second),
findLCS(first, second: second.substringToIndex(second.endIndex.predecessor()))
)
}
}
findLCS("abcdgegdfh", second: "gsabcdehty")
让我们看下playground给我们统计的时间复杂度，===，似乎有点不好看啊，这么久。。。，有点像指数级啊
这个时间复杂度貌似不太像啊
动态规划告诉我们，要避免做重复的运算，就要保存中间结果。那么我们怎么优化呢？
首先，我们的有一个这样的东东result[i,j]来存储中间结果。嗯，看起来是一个二维数组，那么在swift中，我们怎么定义二维数组呢？看下面，实际上苹果给的官方手册上就有。
// : Playground - noun: a place where people can play
import UIKit
struct Array2D<T> {
let row: Int
let columns: Int
var array: Array<T?>
init(row: Int, columns: Int) {
self.columns = columns
self.row = row
array = Array<T?>(count: row * columns, repeatedValue: nil)
}
func indexIsValidForRow(row: Int, column: Int) -> Bool {
return row >= 0 && column >= 0 && row < self.row && column < columns
}
subscript(row: Int, column: Int) -> T? {
get {
assert(indexIsValidForRow(row, column: column), "fuck ,index out of range")
return array[(columns * row) + column]
}
set {
assert(indexIsValidForRow(row, column: column), "fuck ,index out of range")
array[(columns * row) + column] = newValue
}
}
}
func findLCS(first: String, second: String) {
if first.characters.count == 0 || second.characters.count == 0 {
print(0)
}
var result = Array2D<Int>.init(row: first.characters.count + 1, columns: second.characters.count + 1)
for i in 0 ... first.characters.count {
for j in 0 ... second.characters.count {
result[i, j] = 0
}
}
for i in 1 ... first.characters.count {
for j in 1 ... second.characters.count {
print("\(first.characters[first.startIndex.advancedBy(i - 1)])==\(second.characters[second.startIndex.advancedBy(j - 1)])")
if first.characters[first.startIndex.advancedBy(i - 1)] == second.characters[second.startIndex.advancedBy(j - 1)] {
result[i, j] = result[i - 1, j - 1]! + 1
} else {
result[i, j] = max(result[i - 1, j]!, result[i, j - 1]!)
}
// 追踪二维数组变化
for i in 0 ... first.characters.count {
print("[", separator: "", terminator: " ")
for j in 0 ... second.characters.count {
print(result[i, j]!, separator: "", terminator: " ")
}
print("]", separator: "", terminator: "\n")
}
}
}
// 打印最终二维数组情况
for i in 0 ... first.characters.count {
print("[", separator: "", terminator: " ")
for j in 0 ... second.characters.count {
print(result[i, j]!, separator: "", terminator: " ")
}
print("]", separator: "", terminator: "\n")
}
}
findLCS("abcdg", second: "gsacbcdedf")
但是不要高兴得太早了，我们虽然知道了最长子串的长度，但是我们还并不知道最长子串序列是啥，该怎么办呢？
试着想一想，如果我们把这个路径给记录下来，那不就好办了吗？
// : Playground - noun: a place where people can play
import UIKit
enum Direction: Int {
case LEFT_UP = 1
case LEFT
case UP
}
struct Array2D<T> {
let row: Int
let columns: Int
var array: Array<T?>
init(row: Int, columns: Int) {
self.columns = columns
self.row = row
array = Array<T?>(count: row * columns, repeatedValue: nil)
}
func indexIsValidForRow(row: Int, column: Int) -> Bool {
return row >= 0 && column >= 0 && row < self.row && column < columns
}
subscript(row: Int, column: Int) -> T? {
get {
assert(indexIsValidForRow(row, column: column), "fuck ,index out of range")
return array[(columns * row) + column]
}
set {
assert(indexIsValidForRow(row, column: column), "fuck ,index out of range")
array[(columns * row) + column] = newValue
}
}
}
func findLCS(first: String, second: String) {
if first.characters.count == 0 || second.characters.count == 0 {
print(0)
}
var result = Array2D<Int>.init(row: first.characters.count + 1, columns: second.characters.count + 1)
var reverse = Array2D<Int>.init(row: first.characters.count + 1, columns: second.characters.count + 1)
for i in 0 ... first.characters.count {
for j in 0 ... second.characters.count {
result[i, j] = 0
reverse[i, j] = 0
}
}
for i in 1 ... first.characters.count {
for j in 1 ... second.characters.count {
// print("\(first.characters[first.startIndex.advancedBy(i - 1)])==\(second.characters[second.startIndex.advancedBy(j - 1)])")
// 两个相等的情况
if first.characters[first.startIndex.advancedBy(i - 1)] == second.characters[second.startIndex.advancedBy(j - 1)] {
result[i, j] = result[i - 1, j - 1]! + 1
reverse[i, j] = Direction.LEFT_UP.rawValue
} else { // 否则
if result[i - 1, j]! >= result[i, j - 1]! {
result[i, j] = result[i - 1, j]
reverse[i, j] = Direction.UP.rawValue
} else {
result[i, j] = result[i, j - 1]!
reverse[i, j] = Direction.LEFT.rawValue
}
}
// 追踪二维数组变化
// for i in 0 ... first.characters.count {
// print("[", separator: "", terminator: " ")
// for j in 0 ... second.characters.count {
// print(result[i, j]!, separator: "", terminator: " ")
// }
// print("]", separator: "", terminator: "\n")
// }
// print("跟踪回溯数组【left_up=1,left=2,up=3】")
// for i in 0 ... first.characters.count {
// print("[", separator: "", terminator: " ")
// for j in 0 ... second.characters.count {
// print(reverse[i, j]!, separator: "", terminator: " ")
// }
// print("]", separator: "", terminator: "\n")
// }
}
}
print("最长公共子串的长度是\(result[first.characters.count,second.characters.count]!)")
func printLCS(i:Int,j:Int){
if i==0||j==0 {
return
}
if reverse[i,j] == Direction.LEFT_UP.rawValue{
//print(first[first.startIndex.advancedBy(i-1)])//和下面结果一样哦
print("\(second[second.startIndex.advancedBy(j-1)]) -----> [\(i-1),\(j-1)]")
printLCS(i-1, j: j-1)
}else{
if reverse[i,j] == Direction.LEFT.rawValue{
printLCS(i, j: j-1)
}else{
printLCS(i-1, j: j)
}
}
}
printLCS(first.characters.count,j:second.characters.count)
}
findLCS("abwoqjfoafscdg", second: "gsafwejfiojasfcbcdedf")
最终结果
如果敢兴趣的话，可以把注释打开，对这个过程的跟踪会使得你对求最长公共子串的算法有一个更加直观的理解。
