학위논문
시간 제한1초메모리 제한512 MB
긴 책 문자열과 짧은 논문 문자열이 주어질 때 각 테스트마다 두 문자열의 최장 공통 부분 수열 길이를 구한다.
문제
어떤 교수가 학생의 학위논문이 특정 책을 표절한 것이라고 의심하고 있다. 이를 확인하기 위해 교수는 학위논문과 책의 최장 공통 부분 수열을 계산하려고 한다. 마침 그런 프로그램이 없어서, 알고리즘 과목 과제로 이 프로그램을 작성해 달라고 당신에게 부탁했다.
입력
첫째 줄에 테스트 케이스의 수 가 주어진다 (). 그 뒤에 각 테스트 케이스의 설명이 이어진다.
각 테스트 케이스는 두 줄로 주어진다. 첫째 줄에는 길이가 이상 이하인 소문자 라틴 문자로 이루어진 문자열, 즉 책의 텍스트가 주어진다. 둘째 줄에는 길이가 이상 이하인 소문자 라틴 문자로 이루어진 문자열, 즉 학위논문의 텍스트가 주어진다.
모든 테스트 케이스에서 책 길이의 합은 이하이다. 모든 테스트 케이스에서 학위논문 길이의 합은 이하이다.
출력
각 테스트 케이스마다 책과 학위논문의 최장 공통 부분 수열의 길이를 출력한다.