| Submit | All submissions | Best solutions | Back to list |
NAJLCS - Longest Common Subsequence |
The longest common subsequence (LCS) problem is to find the longest subsequence common to all sequences in a set of sequences (often just two). (Note that a subsequence is different from a substring, for the terms of the former need not be consecutive terms of the original sequence.) It is a classic computer science problem, the basis of file comparison programs such as diff, and has applications in bioinformatics.
Given two string A and B print the Longest common subsequence length. All string are lower case alphabetic character.
Input:
The first line of the input contains an integer T (≤ T ≤ 50) denoting the number of test cases. Each test case contains two space separated string A and B. (0≤|A|,|B|≤1000)
Output:
For each test case, display the case number (they are numbered sequentially starting with 1) and the LCS length.
Sample:
|
Input |
Output |
|
2 |
Case 1: 1 |
| Added by: | Najmuzzaman |
| Date: | 2017-05-06 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL LISP clisp D ERL HASK JAVA OCAML PAS-GPC PAS-FPC PERL PHP PICO PIKE PYTHON PYPY PYTHON3 RUBY |
RSS