บทความนี้อธิบายวิธีการของ Java เพื่อค้นหาสายย่อยทั่วไปที่ใหญ่ที่สุดของสองสาย แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
เมื่อเร็ว ๆ นี้ฉันมีข้อกำหนดสำหรับการเปรียบเทียบข้อความในงานโครงการของฉัน หลังจากศึกษาช่วงเวลานี้ฉันได้สรุปเนื้อหาของบล็อกนี้: ค้นหาสายย่อยทั่วไปที่ใหญ่ที่สุดของสองสตริง
แนวคิดอัลกอริทึม: คำนวณสตริงย่อยทั่วไปของสองสายตามกราฟ สำหรับแนวคิดอัลกอริทึมเฉพาะโปรดดูรูปต่อไปนี้:
อินพุตสตริง S1: ACHMACMH อินพุตสตริง S2: Macham
รหัสการใช้งานเฉพาะมีดังนี้:
แพ็คเกจ cn.lulei.compare; นำเข้า java.util.arraylist; นำเข้า Java.util.Collections; นำเข้า Java.util.Comparator; นำเข้า java.util.list; คลาสสาธารณะ Stringcompare {Private int a; ส่วนตัว int b; สตริงสาธารณะ getMaxLengthCommonstring (String S1, String S2) {ถ้า (S1 == NULL || S2 == NULL) {return null; } a = s1.length (); // ความยาว S1 ทำให้บรรทัด b = s2.length (); // ตั้งค่าคอลัมน์ของความยาว S2 ถ้า (a == 0 || b == 0) {return ""; } // ตั้งค่าเมทริกซ์บูลีน [] [] array = บูลีนใหม่ [a] [b]; สำหรับ (int i = 0; i <a; i ++) {char c1 = s1.charat (i); สำหรับ (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}}} // ค้นหาสตริงปัจจัยทั่วไปทั้งหมดบันทึกข้อมูลเป็นตำแหน่งเริ่มต้นและความยาวเมื่อเทียบกับรายการสตริงที่สอง <HildString> ChildStrings = new ArrayList <ChildString> (); สำหรับ (int i = 0; i <a; i ++) {getMaxSort (i, 0, อาร์เรย์, childStrings); } สำหรับ (int i = 1; i <b; i ++) {getMaxSort (0, i, อาร์เรย์, เด็ก); } // เรียงลำดับ (ChildStrings); if (childStrings.size () <1) {return ""; } // ส่งคืนสตริงปัจจัยทั่วไปสูงสุด int max = childStrings.get (0) .MaxLength; StringBuffer sb = new StringBuffer (); สำหรับ (ChildString S: ChildStrings) {ถ้า (สูงสุด! = S.MaxLength) {break; } SB.Append (S2.SubString (S.MaxStart, S.MaxStart + S.MaxLength)); sb.append ("/n"); } return sb.toString (); } // การเรียงลำดับ, การเรียงลำดับเป็นโมฆะส่วนตัวย้อนหลัง (รายการ <ChildString> รายการ) {collections.sort (รายการ, ตัวเปรียบเทียบใหม่ <ChildString> () {public int Compare (ChildString O1, ChildString O2) {return O2.MaxLength - O1.MaxLength;}}); } // ค้นหาสตริงปัจจัยทั่วไปบนช่องว่างส่วนตัว slash getMaxSort (int i, int j, บูลีน [] [] อาร์เรย์, รายการ <ChildString> SortBean) {ความยาว int = 0; int start = j; สำหรับ (; i <a && j <b; i ++, j ++) {ถ้า (อาร์เรย์ [i] [j]) {ความยาว ++; } else {sortBean.add (เด็กใหม่ (ความยาวเริ่มต้น)); ความยาว = 0; start = j + 1; } if (i == a-1 || j == b-1) {sortBean.add (เด็กใหม่ (ความยาวเริ่มต้น)); }}} // ระดับ public factor childString {int maxlength; int maxstart; ChildString (int maxLength, int maxStart) {this.maxLength = maxLength; this.maxStart = maxStart; }} / ** * @param args * / โมฆะคงที่สาธารณะหลัก (สตริง [] args) {// toDo วิธีการที่สร้างอัตโนมัติระบบ Stub System.out.out.println (สตริงใหม่ (). getMaxLengthCommonstring ("achmacmh", "Macham")); - ผลการดำเนินการขั้นสุดท้ายของโปรแกรมคือ:
สำหรับการเปรียบเทียบไฟล์สองไฟล์ฉันคิดว่าแนวคิดอัลกอริทึมนี้สามารถอ้างถึง (และตอนนี้และสำหรับการใช้งาน) ซึ่งจะเขียนในบล็อกในอนาคต
ในกระบวนการดำเนินการข้างต้นข้อมูลสตริงย่อยทั่วไปทั้งหมดจะถูกบันทึกด้วยอาร์เรย์และจากนั้นจึงเรียงลำดับสตริงย่อยที่ใหญ่ที่สุด หากวิธีนี้เป็นเพียงการหาสายย่อยที่ใหญ่ที่สุดอัลกอริทึมนั้นไม่สมเหตุสมผลมากนัก ดังนั้นจึงมีการปรับเปลี่ยนต่อไปนี้ รายการจะบันทึกเฉพาะสายย่อยที่ใหญ่ที่สุดในการคำนวณปัจจุบัน การใช้งานเฉพาะมีดังนี้:
/ ***@คำอธิบาย: การเปรียบเทียบสตริง*/ แพ็คเกจ com.lulei.test; นำเข้า java.util.arraylist; นำเข้า java.util.list; คลาสสาธารณะ Stringcompare {Private int a; ส่วนตัว int b; maxlength ส่วนตัว int ส่วนตัว = -1; สตริงสาธารณะ getMaxLengthCommonstring (String S1, String S2) {ถ้า (S1 == NULL || S2 == NULL) {return null; } a = s1.length (); // ความยาว S1 ใช้ในการทำแถว b = s2.length (); // ความยาว S2 ใช้เพื่อสร้างคอลัมน์ถ้า (a == 0 || b == 0) {return ""; } // ตั้งค่าเมทริกซ์บูลีน [] [] array = บูลีนใหม่ [a] [b]; สำหรับ (int i = 0; i <a; i ++) {char c1 = s1.charat (i); สำหรับ (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}} // เสร็จสิ้นสตริงปัจจัยทั่วไปทั้งหมดและบันทึกข้อมูลเป็นตำแหน่งเริ่มต้นและความยาวเมื่อเทียบกับรายการสตริงที่สอง <HildString> ChildStrings = arrayList ใหม่ <ChildString> (); สำหรับ (int i = 0; i <a; i ++) {getMaxSort (i, 0, อาร์เรย์, childStrings); } สำหรับ (int i = 1; i <b; i ++) {getMaxSort (0, i, อาร์เรย์, เด็ก); } stringBuffer sb = new StringBuffer (); สำหรับ (ChildString S: ChildStrings) {SB.Append (S2.SubString (S.MaxStart, S.MaxStart + S.MaxLength)); sb.append ("/n"); } return sb.toString (); } // ค้นหาสตริงปัจจัยทั่วไปบนช่องว่างส่วนตัว slash getMaxSort (int i, int j, บูลีน [] [] อาร์เรย์, รายการ <ChildString> SortBean) {ความยาว int = 0; int start = j; สำหรับ (; i <a && j <b; i ++, j ++) {ถ้า (อาร์เรย์ [i] [j]) {ความยาว ++; } else {// เพิ่มโดยตรง, บันทึก substrings ทั้งหมด, การตัดสินต่อไปนี้จะบันทึกเฉพาะ substring ที่ใหญ่ที่สุดในปัจจุบัน //sortbean.add( ใหม่ ChildString (ความยาวเริ่มต้น)); if (length == maxLength) {sortBean.add (เด็กใหม่ (ความยาวเริ่มต้น)); } อื่นถ้า (ความยาว> maxLength) {sortBean.clear (); maxlength = ความยาว; SortBean.add (New Childstring (ความยาวเริ่มต้น)); } ความยาว = 0; start = j + 1; } if (i == a-1 || j == b-1) {// เพิ่มโดยตรง, บันทึก substrings ทั้งหมด, การตัดสินต่อไปนี้จะบันทึกเฉพาะ substring ที่ใหญ่ที่สุดในปัจจุบัน //sortbean.add(New ChildString (ความยาวเริ่มต้น)); if (length == maxLength) {sortBean.add (เด็กใหม่ (ความยาวเริ่มต้น)); } อื่นถ้า (ความยาว> maxLength) {sortBean.clear (); maxlength = ความยาว; SortBean.add (New Childstring (ความยาวเริ่มต้น)); }}}}} // ชั้นเรียนสาธารณะคลาส ChildString {int maxlength; int maxstart; ChildString (int maxLength, int maxStart) {this.maxLength = maxLength; this.maxStart = maxStart; }} / ** * @param args * / โมฆะคงที่สาธารณะหลัก (สตริง [] args) {// วิธีการที่สร้างขึ้นอัตโนมัติระบบ Stub System.out.out.println (Stringcompare ใหม่ (). getMaxLengthCommonstring ("ABCDEF" - ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!