Prof. Michal Ziv-Yukelson

A new problem in sequence comparison, given a set of strings S₁, S₂ ... S_c and a target string T S_i = B_iY F_i is introduced. Y is the subsequence common to all of strings S_i. The goal is to compute similarity of all strings S_i with T, without computing the part of Y again and again. How to reduce the O(nl) runtime work for the common subsequence Y in each string to O(n), at the cost of only O(n²+nl) work at preprocessing time, where n is target size and l is the size of Y.