首页 > 代码库 > Longest Common Substring

Longest Common Substring

2024-11-19 01:56:02   202人阅读

Given two strings, find the longest common substring.

Return the length of it.

 Notice

The characters in substring should occur continuously in original string. This is different with subsequence.

Have you met this question in a real interview? Yes
Example
Given A = "ABCD", B = "CBCE", return 2.

Challenge 
O(n x m) time and memory.

区别于 Longest Common Subsequence 这是累加求subString 的

状态设为遍历到当前的i, j时的结果值, 但是却是不对, 是因为求得是累加的值,

Input
 "www.lintcode.com code", "www.ninechapter.com code"
Output
 17
Expected
  9
for (int i = 1; i <= n; i++) {
           for (int j = 1; j <= m; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    f[i][j] = Math.max(f[i - 1][j - 1] + 1, f[i][j]);
                } 
            
            }
        }

和这样写无差异, 都是求的累加和.

if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    f[i][j] = f[i - 1][j - 1] + 1;
                } else {
                    f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
                }

因此要改下状态(根据结果来设定状态需要那几个变量表示, 这个状态跟), : 匹配到的字符是最后一个字符的结果值(作为局部变量 ) + 全局变量

常见状态:

1遍历到当前字符时的最优解,

2 遍历到当前字符,字符如果是题意要求的string的局部解

方程: 分情况讨论, 根据题意与当前字符的形态和上个状态做转化

public int longestCommonSubstring(String A, String B) {
        // write your code here
        //state
        int n = A.length();
        int m = B.length();
        int[][] f = new int[n + 1][m + 1];
        //initialize
        for (int i = 0; i <= n; i++) {
            f[i][0] = 0;
        }
        for (int i = 0; i <= m; i++) {
            f[0][i] = 0;
        }
        int ans = 0;
        //function
        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;
            }
            ans = Math.max(f[i][j], ans);
            
        }
        }
        return ans;
    }

　　

 

　

Longest Common Substring


联系
我们