There are two sequences of characters, for example

abcdebcdeeedde aaadeeed

I am trying to find the largest common subsequence that satisfies a certain condition (an abstract example , the most common general subsequence should contain three e characters), while there is a function to check the subsequence for this condition.

Since the length of the lines is not very long (up to one thousand), I think it makes sense to check in the loop for this condition all General Sequences , starting from the Most Long, until all the General Sequences are moved.

There are a lot of search algorithms for the Greatest Common Subsequence ( LCS ), but no one has set the task to descend into smaller subsequences, if necessary reaching the smallest common subsequence.

    1 answer 1

    Take the search algorithm by dynamic programming. In the process of constructing the matrix, fix the ratio (value-subsequence [-coordinates]) in the additional table for the subsequences that meet the criterion. Upon completion, take the record with the maximum value from the additional table.