Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // 严格的说,这个算法是递推,而不是动态规划,但是可以用动态规划的四要素去分析换个解答。
- // 为什么不是动态规划?因为最暴力的方式也就是 O(n^3) 可以找到A所有的Substring然后看看在不在B里。
- public class Solution {
- /**
- * @param A, B: Two string.
- * @return: the length of the longest common substring.
- */
- public int longestCommonSubstring(String A, String B) {
- // state: f[i][j] is the length of the longest lcs
- // ended with A[i - 1] & B[j - 1] in A[0..i-1] & B[0..j-1]
- int n = A.length();
- int m = B.length();
- int[][] f = new int[n + 1][m + 1];
- // initialize: f[i][j] is 0 by default
- // function: f[i][j] = f[i - 1][j - 1] + 1 or 0
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- if (A.charAt(i - 1) == B.charAt(j - 1)) {
- f[i][j] = f[i - 1][j - 1] + 1;
- } else {
- f[i][j] = 0;
- }
- }
- }
- // answer: max{f[i][j]}
- int max = 0;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- max = Math.max(max, f[i][j]);
- }
- }
- return max;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement