Friday, September 13, 2013

WAP to find longest repeating subsequence

String longestSubstr(String str, String toCompare) {
        if (str == null || toCompare == null) {
            return null;
        }
        int[][] compareTable = new int[str.length()][toCompare.length()];
        int maxLen = 0;
        StringBuilder res = new StringBuilder();
        int m = 0, n = 0;
        for (; m < str.length(); m++) {
            for (; n < toCompare.length(); n++) {
                compareTable[m][n] = (str.charAt(m) != toCompare.charAt(n)) ? 0
                        : (((m == 0) || (n == 0)) ? 1
                        : compareTable[m - 1][n - 1] + 1);
                maxLen = (compareTable[m][n] > maxLen) ? compareTable[m][n]
                        : maxLen;
            }
        }
        for (int i = m + 1 - maxLen; i < m; i++) {
            res.append(str.charAt(i));
        }
        return res.toString();
    }

No comments:

Post a Comment