HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Dynamic programming & Greedy > problem:


50673 - DNA Testing

Guest
• Discussion of problem (1)

Section problems

• 50676 - Cinema Millennium
• 50678 - The Jumping Rabbit
• 51149 - One Piece Arena
• 50485 - Center of gravity of a plate
• 50674 - Collecting Eggs
• 50677 - The Cottage
• 50675 - Kruja Boys
• 50679 - Jetpack Hurdle Jumping
• 50673 - DNA Testing
• 50997 - Dynamic Knights
• 50936 - Saving the Soldiers
• 50979 - Minimum access cost for BST
• 51062 - Fish Pond II
• 51010 - Max Sequential Sum
• 51072 - Castle on chessboard
• 51075 - Shortest Path for Bishop
• 50688 - Epoka Furgon

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Arnold Drita.

DNA Tester

Scientists have recently found a new planet able to sustain life. Not only that, but this planet also has some life forms similair to those on earch.
Our job is, to analyse the DNA samples from those life forms, and compare them to DNA samples from our own creatures, and find the longest matching substring.


Input specification
First, you will be given two numbers, n and m : 1<=n,m<=2000, representing the length of the two strings. Then you will be given the strings themselves.

Output specification
Give the length of the longest matching DNA string on both DNA samples. Note, the DNA from creatures of our planet consists of only (A, T, C, G), but the DNA from the other planet can have any character from A to Z.


Input I
10 5
AMKGLCUITE
AGCTA
Output 1
4
     
Input 2
15 7
QWERTYUIOPAICUG
ATCGACT
Output 2
3

Для отправки решений необходимо выполнить вход.

www.contester.ru