Longest Common Subsequence

View as PDF
Submit solution
Points: 7
Time limit: 1.0s
Memory limit: 256M
Author:
FatalEagle
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Solve the Longest Common Subsequence problem.

Input Specification

Line 1: N, M (1 \le N, M \le 1\,000)

Line 2: N nonnegative integers \le 1\,000, the first sequence.

Line 3: M nonnegative integers \le 1\,000, the second sequence.

Output Specification

Line 1: The length of the LCS of the first and second sequences.

Sample Input

5 3
1 4 3 4 2
2 1 3

Sample Output

2

Comments


  • 4
    Roronoa_Zoro1540  commented on June 22, 2018, 7:23 p.m. ← edit 2

    nvm


  • -6
    bobhob314  commented on June 19, 2015, 3:32 p.m. ← edited

    This comment is hidden due to too much negative feedback. Click here to view it.


    • 10
      kobortor  commented on June 19, 2015, 4:04 p.m.

      The test case can have multiple digit numbers you know

      print(input()) gives

      9 1 1 0 2 3 10 3 0

      not

      9 1 1 0 2 3 1 0 3 0