Longest Common Subsequence with Substring Constraints

This problem requires you to find the longest common subsequence (LCS) of two sequences X and Y that satisfies additional substring constraints. In other words, given two sequences X and Y (of lengths n and m respectively) and a set of k constraint strings \(S = \{S_1, S_2, \dots, S_k\}\), you are to find a longest common subsequence \(Z\) of X and Y such that each \(S_i\) (for \(1 \le i \le k\)) appears as a substring (i.e. as consecutive characters) in \(Z\>.

Note: A substring is a contiguous block of characters. For instance, if \(T = t_1t_2\dots t_n\), then a string of the form \(t_{i}t_{i+1}\dots t_{j}\) (with \(1 \le i \le j \le n\)) is a substring of \(T\), while any sequence of characters selected in order that is not contiguous is only a subsequence but not a substring.

Example: For X = actaagacct, Y = gacctacctc and constraint set S = {ata, tact}, the unconstrained LCS actacct does not satisfy the constraints. The answer is atact which is the longest common subsequence containing both ata and tact as substrings.

Your task is to design an algorithm that, given the sequences and constraints, computes such a subsequence. If no common subsequence satisfying the constraints exists, output 0.

inputFormat

The input consists of several lines:

• The first line contains the string X.
• The second line contains the string Y.
• The third line contains an integer k, the number of constraint strings.
• Each of the following k lines contains one constraint string.

All strings consist of lowercase English letters.

outputFormat

If there exists a common subsequence of X and Y that contains every one of the constraint strings (each as a substring), output the longest such subsequence. If no such subsequence exists, print 0.

sample

actaagacct
gacctacctc
2
ata
tact

atact