Strings are difficult, most of the contest programmers say this and try to avoid string algorithms. But actually strings are fun and not that difficult. It's just that we don't try hard enough and haven't grown that confidence in ourselves.
And there are many very good problems which you may think need difficult string algorithms to solve but actually they are very easy and straightforward if you know some simple tricks.
Now, you will be given a string related problem. Can you solve this and prove that strings aren't that difficult :D.
Given three strings A, B and C.
Find the longest common sub-sequence of A and B, which have C at-least once as a substring in it.
There will be T (1 ≤ T ≤ 100) test cases.
For each test there will be three lines describing string A, B, and C (1 ≤ |A|, |B|, |C| ≤ 100). |S| defines the length of string S.
Note: Do not use gets() or getline() functions. normal scanf() or cin is good enough.
For each test case output one lines. First the case number then the length of the longest such string .
| Input | Output |
|---|---|
1 AB AB A | Case 1: 2 |