Longest Common Substring

Description

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.

Example
Given A = "ABCD", B = "CBCE", return 2.

Challenge:
O(n x m) time and memory.

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

class Solution {
public:    
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    int longestCommonSubstring(string &s1, string &s2) {
        // write your code here
        if (s1.empty() || s2.empty()) {
            return 0;
        }
        int n1 = s1.size();
        int n2 = s2.size();
        int maxlen = 0;
        for (int i = 0; i < n1; ++i) {
            for (int j = 0; j < n2; ++j) {
               int len = 0;
                while (i + len < n1 && j + len < n2 
                       && s1[i + len] == s2[j + len]) {
                    len++;
                }
                maxlen = max(maxlen, len);
            }
        }
        return maxlen;
    }
};

Similar problems

x

Tags

x