1019 : DNA
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)
ดีเอ็นเอ (Deoxyribonucleic acid) คือ สารพันธุกรรมที่สามารถนำมาใช้เป็นเอกลักษณ์ของสิ่งมีชีวิต โดยดีเอ็นเอนี้เมื่อผ่านการถอดความหมายมาจากสารพันธุกรรมใดๆแล้วจะถูกนำมาเก็บในลักษณะของสายอักขระ โดยตัวอักขระนั้นจะมีเพียงแค่สี่ตัวเท่านั้น นั่นคือ A C G และ T
ในการวิเคราะห์ดีเอ็นเอของคุณหญิงหมอ มักประสบปัญหาที่ข้อมูลที่ต้องการเปรียบเทียบแม้ว่าสิ่งมีชีวิตชนิดเดียวกันแต่ตำแหน่งเริ่มต้นไม่ตรงกันทำให้ยากที่จะเปรียบเทียบกันได้ ตัวอย่างเช่น สารชนิดแรกได้ผลมาเป็น AAAACTGCTACCGGT และชิ้นที่สองคือ CTGAATCTACTGCTATTGCAA หากสังเกตให้ดีจะเห็นได้ว่าส่วนที่เหมือนกันที่มีความยาวต่อเนื่องมากที่สุดคือ ACTGCTA
ข้อมูลที่ซ้ำและยาวที่สุดอาจมีได้หลายชุด หน้าที่ของเราคือเขียนโปรแกรมเพื่อช่วยคุณหญิงหมอหาส่วนที่เหมือนกันอย่างต่อเนื่องของดีเอ็นเอจำนวน 2 สาย
ข้อมูลนำเข้า
บรรทัดแรกและบรรทัดที่สอง แต่ละบรรทัดเก็บข้อมูลของดีเอ็นเอแต่ละสาย โดยแต่ละสายจะประกอบด้วยอักขระ ‘A’ ‘C’ ‘G’ ‘T’ เท่านั้น โดยความยาวของแต่ละสายเป็น L โดยที่ 1 < L < 200
ข้อมูลส่งออก
บรรทัดแรก เป็นแสดง ส่วนที่เหมือนกันที่ยาวที่สุด ของดีเอ็นเอทั้งสองสาย ถ้ามีส่วนที่ยาวที่สุดมากกว่าหนึ่งคำตอบให้เลือกตอบส่วนที่ยาวที่สุดสายแรกที่พบ
("สายแรก" หมายถึง สายย่อยที่อยู่ซ้ายที่สุดของดีเอ็นเอสายแรก)
ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2547
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
ในการวิเคราะห์ดีเอ็นเอของคุณหญิงหมอ มักประสบปัญหาที่ข้อมูลที่ต้องการเปรียบเทียบแม้ว่าสิ่งมีชีวิตชนิดเดียวกันแต่ตำแหน่งเริ่มต้นไม่ตรงกันทำให้ยากที่จะเปรียบเทียบกันได้ ตัวอย่างเช่น สารชนิดแรกได้ผลมาเป็น AAAACTGCTACCGGT และชิ้นที่สองคือ CTGAATCTACTGCTATTGCAA หากสังเกตให้ดีจะเห็นได้ว่าส่วนที่เหมือนกันที่มีความยาวต่อเนื่องมากที่สุดคือ ACTGCTA
ข้อมูลที่ซ้ำและยาวที่สุดอาจมีได้หลายชุด หน้าที่ของเราคือเขียนโปรแกรมเพื่อช่วยคุณหญิงหมอหาส่วนที่เหมือนกันอย่างต่อเนื่องของดีเอ็นเอจำนวน 2 สาย
ข้อมูลนำเข้า
บรรทัดแรกและบรรทัดที่สอง แต่ละบรรทัดเก็บข้อมูลของดีเอ็นเอแต่ละสาย โดยแต่ละสายจะประกอบด้วยอักขระ ‘A’ ‘C’ ‘G’ ‘T’ เท่านั้น โดยความยาวของแต่ละสายเป็น L โดยที่ 1 < L < 200
ข้อมูลส่งออก
บรรทัดแรก เป็นแสดง ส่วนที่เหมือนกันที่ยาวที่สุด ของดีเอ็นเอทั้งสองสาย ถ้ามีส่วนที่ยาวที่สุดมากกว่าหนึ่งคำตอบให้เลือกตอบส่วนที่ยาวที่สุดสายแรกที่พบ
("สายแรก" หมายถึง สายย่อยที่อยู่ซ้ายที่สุดของดีเอ็นเอสายแรก)
ที่มา: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2547
| ตัวอย่างข้อมูลนำเข้า | ตัวอย่างข้อมูลส่งออก |
| AAAACTGCTACCGGT CTGAATCTACTGCTATTGCAA | ACTGCTA |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 5 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)