Longest Common Subsequence of Two Strings containing a particular Substring A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Given three strings A, B and C (note the order) as input, find the length of the longest string S such that:


Condition 1: S is a subsequence of A
Condition 2: S is a subsequence of B
Condition 3: C is a substring of S


.

Testcase #1


Input:

ABCDEF

CDEFAB

B

Output:

2

Testcase #2


Input:

HELLO

WORLD

SUCKS

Output:

0

Testcase #3


Input:

ABCXD

BCDEF

CD

Ouput:

3

Testcase #4


Input:

X

Y

Z

Ouput:

0

Note:


The empty string is regarded as a subsequence as well as a substring of every string.
Assume all input strings are in uppercase.
Return 0 as output if any of the first two conditions (Condition 1 and Condition 2) is not going to be satisfied using Condition 3.


Constraints:


Assume the lengths of A, B and C will always be between 1 and 3000 (both inclusive)


Winner:

One with the shortest code.
APL (45)

⌈/0,⍴¨m/⍨∨/¨⍞∘⍷¨m←⊃∩/{/∘⍵¨↓⍉(z/2)⊤⍳2*z←⍴⍵}¨⍞⍞


Explanation:


¨⍞⍞: read two lines. For each of them:

⍳2*z←⍴⍵: get the numbers from 1 up to 2^length. 
(z/2)⊤: encode each number as bits
↓⍉: separate each string of bits into its own array
/∘⍵¨: and use each of them as a bitmask on the string, giving the subsequences

m←⊃∩/: take the intersection of the two arrays of subsequences, store in m
∨/¨⍞∘⍷¨: read a third line, and see in which subsequences it occurs
m/⍨: select those elements from m that contained the third line
⍴¨: get the length of each remaining subsequence
0,: add a zero entry in case the resulting list is empty
⌈/: get the highest number in the list


Test cases:

      ⌈/0,⍴¨m/⍨∨/¨⍞∘⍷¨m←⊃∩/{/∘⍵¨↓⍉(z/2)⊤⍳2*z←⍴⍵}¨⍞⍞
ABCDEF
CDEFAB
B
 2 
      ⌈/0,⍴¨m/⍨∨/¨⍞∘⍷¨m←⊃∩/{/∘⍵¨↓⍉(z/2)⊤⍳2*z←⍴⍵}¨⍞⍞
HELLO
WORLD
SUCKS
 0
      ⌈/0,⍴¨m/⍨∨/¨⍞∘⍷¨m←⊃∩/{/∘⍵¨↓⍉(z/2)⊤⍳2*z←⍴⍵}¨⍞⍞
ABCXD
BCDEF
CD
 3 
      ⌈/0,⍴¨m/⍨∨/¨⍞∘⍷¨m←⊃∩/{/∘⍵¨↓⍉(z/2)⊤⍳2*z←⍴⍵}¨⍞⍞
X
Y
Z
 0