Longest Common Subsequence Again

Time Limit: 2000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 2253
64-bit integer IO format: %I64d      Java class name: Main

Description

Everyone knows LCS problem:

For example:
str1 = "GCTAT"
str2 = "CGATTA"

the longest common subsequence is "GTT" of them.So you should print "3".

I'm sure you can easily sovle it.So the challenge is coming again.(^_^)

Input

For each case,there are two lines.one is string A,the other is string B.
the string Process to end of file.Each string will have at most 30000 characters.
All the characters are in upper-case.

Output

For each case, output the maximum-length common subsequence.

Sample Input

GCTAT
CGATTA 

ABCFBC
ABFCAB

Sample Output

3
4

Source

Language: 
Theme: 
Share Code? 

Powered by NB231 | Current Style: .