1019.html

<span style="font-family: Courier New;"><strong>ดีเอ็นเอ (Deoxyribonucleic acid)</strong> คือ สารพันธุกรรมที่สามารถนำมาใช้เป็นเอกลักษณ์ของสิ่งมีชีวิต โดยดีเอ็นเอนี้เมื่อผ่านการถอดความหมายมาจากสารพันธุกรรมใดๆแล้วจะถูกนำมาเก็บในลักษณะของสายอักขระ โดยตัวอักขระนั้นจะมีเพียงแค่สี่ตัวเท่านั้น นั่นคือ A C G และ T <br />
<br />
ในการวิเคราะห์ดีเอ็นเอของคุณหญิงหมอ มักประสบปัญหาที่ข้อมูลที่ต้องการเปรียบเทียบแม้ว่าสิ่งมีชีวิตชนิดเดียวกันแต่ตำแหน่งเริ่มต้นไม่ตรงกันทำให้ยากที่จะเปรียบเทียบกันได้ ตัวอย่างเช่น สารชนิดแรกได้ผลมาเป็น AAAACTGCTACCGGT และชิ้นที่สองคือ CTGAATCTACTGCTATTGCAA หากสังเกตให้ดีจะเห็นได้ว่าส่วนที่เหมือนกันที่มีความยาวต่อเนื่องมากที่สุดคือ ACTGCTA <br />
<br />
ข้อมูลที่ซ้ำและยาวที่สุดอาจมีได้หลายชุด หน้าที่ของเราคือเขียนโปรแกรมเพื่อช่วยคุณหญิงหมอหาส่วนที่เหมือนกันอย่างต่อเนื่องของดีเอ็นเอจำนวน 2 สาย <b><br />
</b><u><b><br />
ข้อมูลนำเข้า</b></u><b><br />
บรรทัดแรกและบรรทัดที่สอง </b>แต่ละบรรทัดเก็บข้อมูลของดีเอ็นเอแต่ละสาย โดยแต่ละสายจะประกอบด้วยอักขระ &lsquo;A&rsquo; &lsquo;C&rsquo; &lsquo;G&rsquo; &lsquo;T&rsquo; เท่านั้น โดยความยาวของแต่ละสายเป็น L โดยที่ 1 &lt; L &lt; 200 <b><br />
<br />
</b><u><b>ข้อมูลส่งออก</b></u><br />
<b>บรรทัดแรก</b> เป็นแสดง ส่วนที่เหมือนกันที่ยาวที่สุด ของดีเอ็นเอทั้งสองสาย ถ้ามีส่วนที่ยาวที่สุดมากกว่าหนึ่งคำตอบให้เลือกตอบส่วนที่ยาวที่สุดสายแรกที่พบ<br />
(&quot;สายแรก&quot; หมายถึง สายย่อยที่อยู่ซ้ายที่สุดของดีเอ็นเอสายแรก)<b><br />
<br />
<u>ที่มา</u>: การแข่งขันคณิตศาสตร์ วิทยาศาสตร์ โอลิมปิกแห่งประเทศไทย สาขาวิชาคอมพิวเตอร์ ประจำปี 2547</b></span>
		<table>
			<tr>
				<th>ข้อมูลนำเข้า</th>
				<th>ข้อมูลส่งออก</th>
			</tr>	
		
			<tr>
				<td>AAAACTGCTACCGGT
<br />CTGAATCTACTGCTATTGCAA</td>
				<td>ACTGCTA</td>
			</tr></table>