시간 제한 | 메모리 제한 | 제출 | 정답 | 맞은 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 512 MB | 41 | 19 | 14 | 56.000% |
A professor suspects that a student's dissertation was plagiarized from a certain book. In order to test that, he wants to compute the longest common subsequence of the dissertation and the book. He doesn't have a program to do it, so he asked you to write such a program as an assignment for the algorithms course.
The first line of input contains the number of test cases $z$ ($1 \leq z \leq 10^9$). The descriptions of the test cases follow.
Each test case is given on two lines. The first line contains a string of length between $1$ and $1\,000\,000$ consisting of lowercase Latin letters: the text of the book. The second line contains a string of length between $1$ and $1000$ consisting of lowercase Latin letters: the text of the dissertation.
The sum of lengths of the books in all test cases is at most $10\,000\,000$. The sum of lengths of the dissertations in all test cases is at most $30\,000$.
For each test case, output the length of the longest common subsequence of the book and the dissertation.
1 abcdefghijklmnopqrstuvwxyz bbddee
3