Longest common substring problem

发表于   |   分类于 ， ，

In computer science, the longest common substring problem is to find the longest string (or strings) that is a substring (or are substrings) of two or more strings.- - - - wikipedia

描述

最长公共子串，要求所求得的字符串在原字符串中必须是连续的

分析

动态规划思想，以一个二维数组来存储子串长度

若要求出所有的最长公共子串，可以在填充数组时（或者填充完毕后遍历一遍数组），将最长公共子串的末尾位置（即数组内的最大值）记录下来。因为这时已知最长公共子串的长度，所以便很容易知道其起始位置，即可得到子串

优化：因为 L[i][j] 只和 L[i - 1][j - 1] 有关，所以可以通过把数组折叠的方法，来减少占用的空间

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {

    public int LCSubstr(String S, String T) {

        S = " " + S;
        T = " " + T;
        int[][] L = new int[S.length()][T.length()];
        int maxLen = 0;

        for (int i = 1; i < S.length(); i++) {
            for (int j = 1; j < T.length(); j++) {

                if (S.charAt(i) == T.charAt(j)) {
                    L[i][j] = L[i - 1][j - 1] + 1;
                    if (maxLen < L[i][j]) {
                        maxLen = L[i][j];
                    }
                }
            }
        }

        return maxLen;
    }
}