Description: Longest common subsequence problem
Description and Purpose:
Z = <B,C,D,B> sequence is the sequence X = <A,B,C,B,D,A,B> the sequence, the corresponding sequence of increasing subscript <2,3,5,7 >.
In general, given a sequence X = <x1,x2,…,xm>, then another sequence Z = <z1,z2,…,zk> is a sub-sequence of X, is the existence of a strictly increasing sequence subscript <i1,i2,…,ik> such that for all j = 1,2, ..., k so that the first j elements Z zj and X the same as the first element ij.
Given two sequences X and Y, when another sequence Z as X, Y promoter sequence is a sub sequence, said sequence of X and Y Z is the common subsequence.
Your task is: given two sequences X, Y, X and Y find the longest common subsequence Z.
Input sample
2
76
A B C B D A B
B D C A B A
89
b a a b a b a b
a b a b b a b b a
Output
Case 1
4 LCS (X, Y): B C B A
Case 2
6 LCS (X, Y): a b a b a b
To Search:
File list (Check if you may need any files):
LCS\LCS.CPP
...\LCS.dsp
...\LCS.dsw
...\LCS.opt
...\LCS.plg
...\LCS.ncb
...\LCS.vcproj
...\LCS.sln
...\LCS.suo
...\Debug\LCS.exe
...\.....\vc60.idb
...\.....\vc60.pdb
...\.....\BuildLog.htm
...\.....\vc70.pdb
...\.....\vc70.idb
...\.....\Lcs.obj
...\.....\LCS.pch
...\.....\LCS.pdb
...\Debug
LCS
Download