Longest common substring problem suffix array
类似的,还有
Longest Repeated Substring suffix array
下面的都是刷题的DP:
最长公共子串(Longest Common Substring): 是指两个字符串中最长连续相同的子串长度。
例如:str1=“1AB2345CD”,str2=”12345EF”,则str1,str2的最长公共子串为2345。
解法1
如果 str1 的长度为 N,str2 的长度为 M,生成大小为 N*M 的 数组 dp , dp[i][j]表示 str1[0…i] 与 str2[0…j] 的
最长公共子串的长度。
计算dp[i][j] 的方法如下:
- 矩阵 dp 的第一列 dp[0…m-1][0].对于 某个位置(i,0)如果str1[i]==str2[0],则dp[i][0]=1,否则dp[i][0]=0
- 矩阵 dp 的第一行 dp[0][0…n-1].对于 某个位置(0,j)如果str1[0]==str2[j],则dp[0][j]=1,否则dp[0][j]=0
- 其他位置从左到右从上到下计算,dp[i][j]的值只有两种情况:
1). str1[i]==str2[j],dp[i][j]=dp[i-1][j-1]+1;
2). tr1[i]!=str2[j]则dp[i][j]=0;
str1=”abc”,str2=”caba”的 dp 矩阵如下:
- 1
c 0 0 1
a 1 0 0
b 0 2 0
a 1 0 0
代码:
- 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
解法2
经典动态规划的方法需要大小为M*N的 dp 矩阵,但实际上是可以减少至O(1)的,因为计算每一个dp[i][j]的时候只需要计算dp[i-1][j-1],所以按照斜线方向计算所有的值,只需要一个变量就可以计算:
No comments:
Post a Comment