Problem Statement:
Given two strings a,b of length m and n (1<=m,n<=1000) which only contains 'A' and 'B' letters, there are k<=100 queries.
For each query: Given string S of length m+n, check if this string can be form by string a,b by keeping their original order.
(let's a = {x0,x1,x2,...,xm} , b = {y0,y1,y2,....,yn} ; S may be {x0,x1,y0,x2,y1,y2,x3,...} or something like this : position of x0<x1<x2<...<xm and position of y0<y1<y2<...<yn)
More formally: string a and b must be subsequence of string S which doesn't use the same postition of S twice.
For example:
let a = "BAB" , b = "AB" ==> Posible string S is "BAABB" ,"BABAB", "ABBAB" but not "BBABA"
how to solve this problem? I think it's dynamic programming problem. Thank you very much in advance.
Full text and comments »