| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
PTIT137D - BÀI D - DNA |
Người ta biểu diễn các chuỗi DNA dưới dạng các xâu ký tự với bốn chữ cái: A, T, G, C. Khi các biểu diễn DNA của nhiều người có một đoạn (là một chuỗi kí tự liên tiếp) giống nhau thì nhiều khả năng họ sẽ có chung nguồn gốc.
Bài toán đặt ra là cho trước biểu diễn DNA của nhiều người. Hãy tìm đoạn chung dài nhất trong các chuỗi DNA đó.
Input
- Dòng đầu tiên chứa số n là số bộ test (không quá 100). Mỗi bộ test gồm:
- Một số nguyên m (2<=m<=10) là số dãy DNA được xem xét.
- m dòng tiếp theo, mỗi dòng chứa biểu diễn của một chuỗi DNA có đúng 60 ký tự.
Output
- Với mỗi bộ test, in ra màn hình, trên một dòng, đoạn chung của các chuỗi DNA.
Nếu nhiều đoạn chung có cùng độ dài lớn nhất thì in ra đoạn đầu tiên theo thứ tự từ điển.
Nếu không có đoạn chung hoặc đoạn chung ít hơn 3 ký tự thì in ra
“no significant commonalities”.
Example
Input:
3
2
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
3
GATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATACCAGATA
GATACTAGATACTAGATACTAGATACTAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
GATACCAGATACCAGATACCAGATACCAAAGGAAAGGGAAAAGGGGAAAAAGGGGGAAAA
3
CATCATCATCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
ACATCATCATAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AACATCATCATTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Output:
no significant commonalities
AGATAC
CATCATCAT
| Được gửi lên bởi: | adm |
| Ngày: | 2013-03-24 |
| Thời gian chạy: | 5s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
hide comments
|
2018-08-06 20:01:25
Hmm, sao lại sai ta, đúng full test rồi mà.-_- |
|
|
2014-06-07 10:53:46 Hướng Thái Dương
nguồn olympic tin học sinh viên |
