| Submit | All submissions | Best solutions | Back to list |
NAJLG - 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 abadsfaf ajfkfjj |
Case 1: 1 Case 2: 3 |
| Added by: | Najmuzzaman |
| Date: | 2015-03-13 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ADA95 ASM64 MAWK BC C-CLANG NCSHARP CPP14-CLANG COFFEE D-CLANG D D-DMD DART ELIXIR ERL FANTOM FORTH JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY3 R RACKET RUST SCALA SCM guile SCM qobi CHICKEN SED ST SQLITE SWIFT UNLAMBDA WHITESPACE |
RSS