Definition of the problem
The input of the problem consists of two finite lists:
- u1, ..., un and v1, ..., vn
of words over some alphabet Σ with at least two symbols. A solution to this problem is a sequence of indexes i1, ..., ik, 1 <= ij <= n, such that
- ui1...uik = vi1...vik.
The decision problem then is to decide whether such a solution exists or not.
Example of an instance of the problem
Consider the following two lists:
u1 u2 u3 u4 v1 v2 v3 v4
"aba" "bbb" "aab" "bb" "a" "aaa" "abab" "babba"
A solution to this problem would be the sequence 1, 4, 3, 1 because
- u1u4u3u1 = "ababbaababa" = v1v4v3v1
If the two lists would have consisted of, for example, only u1, u2, u3 and v1, v2, v3 then there would have been no solution.