Longest Contiguous Common Subsequence

longest_contiguous_common_subsequence.py

def to_ngrams(s, minimum_n):
    """Generate n-grams (len(string) >= n >= minimum) from string
    Params:
        <str> s
        <int> minimum
    Return:
        <set <str>> ngrams
    """
    ngrams = []
    length = len(s)
    for i in xrange(length-1):
        ngrams += [s[i:j] for j in xrange(i+minimum_n, length+1)]
    return set(ngrams)

def longest_contiguous_common_subsequence(lhs, rhs, minimum_n):
    """
    Params:
        <str> lhs
        <str> rhs
        <int> minimum_n
    Return:
        <str> longest_contiguous_common_subsequence
    """
    if len(lhs) < minimum_n or len(rhs) < minimum_n:
        return None
    lhs = self.to_ngrams(lhs, minimum_n)
    rhs = self.to_ngrams(rhs, minimum_n)
    common_subsequences = lhs & rhs
    if common_subsequences:
        return sorted(common_subsequences, key=lambda x: len(x), reverse=True)[0]