-
Notifications
You must be signed in to change notification settings - Fork 17
/
MaxSameLength.kt
61 lines (52 loc) · 1.82 KB
/
MaxSameLength.kt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package com.daily.algothrim.dp
import kotlin.math.max
/**
* 最多公共子串长度
* 求把一个字符串变成另一个字符串,可以进行编辑,但只可以进行增加与删除
* 求编辑过程中原子串最多的公共长度
*/
class MaxSameLength {
companion object {
@JvmStatic
fun main(args: Array<String>) {
println(MaxSameLength().maxSameLength("mitcmu".toCharArray(), "mtacnu".toCharArray(), 6, 6))
}
}
fun maxSameLength(a: CharArray, b: CharArray, n: Int, m: Int): Int {
val status = Array(n) { IntArray(m) }
var p = 0
while (p < n) { // 初始化第一列
when {
a[p] == b[0] -> status[p][0] = 1
p != 0 -> status[p][0] = status[p - 1][0]
else -> status[p][0] = 0
}
p++
}
var q = 0
while (q < m) { // 初始化第一行
when {
a[0] == b[q] -> status[0][q] = 1
q != 0 -> status[0][q] = status[0][q - 1]
else -> status[0][q] = 0
}
q++
}
// 1. a[n] == b[m] status[n][m] = max(status[n-1][m], status[n][m-1], status[n-1][m-1] + 1)
// 2. a[n] != b[m] status[n][m] = max(status[n-1][m], status[n][m-1], status[n-1][m-1])
var k = 1
while (k < n) { // 填充剩余的行列,按行填充
var j = 1
while (j < m) {
if (a[k] == b[j]) {
status[k][j] = max(max(status[k - 1][j], status[k][j - 1]), status[k - 1][j - 1] + 1)
} else {
status[k][j] = max(max(status[k - 1][j], status[k][j - 1]), status[k - 1][j - 1])
}
j++
}
k++
}
return status[n - 1][m - 1]
}
}