تصف هذه المقالة طريقة 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 (السلسلة S1 ، السلسلة S2) {if (s1 == null || s2 == null) {return null ؛ } a = s1.length () ؛ // s1 طول يجعل السطر b = s2.length () ؛ // قم بتعيين عمود طول S2 if (a == 0 || b == 0) {return "" ؛ } // قم بتعيين مصفوفة مطابقة Boolean [] [] [] Array = New Boolean [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 ؛ } آخر {array [i] [j] = false ؛ }}}} // ابحث عن جميع سلاسل العوامل المشتركة ، وإنقاذ المعلومات كموقف البداية وطولها بالنسبة لقائمة السلسلة الثانية <HividString> childstrings = new ArrayList <HividString> () ؛ لـ (int i = 0 ؛ i <a ؛ i ++) {getMaxSort (i ، 0 ، array ، childstrings) ؛ } لـ (int i = 1 ؛ i <b ؛ i ++) {getMaxSort (0 ، i ، array ، childstrings) ؛ } // فرز الفرز (childstrings) ؛ if (childstrings.size () <1) {return "" ؛ } // إرجاع الحد الأقصى لسلسلة العامل المشترك int max = childstrings.get (0) .MaxLength ؛ StringBuffer SB = New StringBuffer () ؛ لـ (childstring s: childstrings) {if (max! = s.maxLength) {break ؛ } sb.append (s2.SubString (S.MaxStart ، S.MaxStart + S.MaxLength)) ؛ sb.append ("/n") ؛ } return sb.toString () ؛ } // sorting ، flashback private void sort (list <HividString> list) {collections.sort (list ، New Nealth <HividString> () {public int compare (childstring o1 ، childstring o2) {return o2.maxlength - o1.maxlength ؛}}) ؛ } // ابحث عن سلسلة العوامل المشتركة على void private getMaxSort (int i ، int j ، boolean [] [] ، قائمة <HividString> sortbean) {int length = 0 ؛ int start = j ؛ لـ (؛ i <a && j <b ؛ i ++ ، j ++) {if (array [i] [j]) {length ++ ؛ } آخر {sortbean.add (New ChildString (طول ، ابدأ)) ؛ الطول = 0 ؛ ابدأ = j + 1 ؛ } if (i == a-1 || j == b-1) {sortbean.add (New ChildString (length ، start)) ؛ }}} // فئة العامل العام childString {int maxLength ؛ int maxstart. childstring (int maxlength ، int maxStart) {this.maxLength = maxLength ؛ this.maxStart = maxStart ؛ }} / ** * param args * / public static void main (string [] args) {// todo method method method system.out.println (new StringCompare (). }} نتيجة التنفيذ النهائية للبرنامج هي:
لمقارنة الملفين ، أعتقد شخصياً أنه يمكن إحالة هذه الفكرة الخوارزمية (والآن وللنطق) ، والتي سيتم كتابتها في مدونة مستقبلية.
في عملية التنفيذ أعلاه ، يتم حفظ جميع المعلومات الفرعية المشتركة مع صفيف ، ثم يتم فرز أكبر فرعية. إذا كانت هذه الطريقة هي مجرد العثور على أكبر فرعية ، فإن الخوارزمية ليست معقولة جدًا. لذلك ، يتم إجراء التعديلات التالية. قائمة فقط يحفظ أكبر فرعية في الحساب الحالي. التنفيذ المحدد هو كما يلي:
/ ***@الوصف: مقارنة السلسلة*/ package com.lulei.test ؛ استيراد java.util.arraylist ؛ استيراد java.util.list ؛ الفئة العامة stringCompare {private int a ؛ الخاص int b ؛ private int maxlength = -1 ؛ السلسلة العامة getMaxLengthCommonstring (السلسلة S1 ، السلسلة S2) {if (s1 == null || s2 == null) {return null ؛ } a = s1.length () ؛ // s1 طول استخدام الصف b = s2.length () ؛ // s2 يتم استخدام طول لجعل العمود إذا (a == 0 || b == 0) {return "" ؛ } // قم بتعيين مصفوفة مطابقة Boolean [] [] [] Array = New Boolean [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 ؛ } آخر {array [i] [j] = false ؛ }}} // الانتهاء من جميع سلاسل العوامل الشائعة وحفظ المعلومات كموضع البداية وطولها بالنسبة إلى قائمة السلسلة الثانية <HividString> childStrings = new ArrayList <HividString> () ؛ لـ (int i = 0 ؛ i <a ؛ i ++) {getMaxSort (i ، 0 ، array ، childstrings) ؛ } لـ (int i = 1 ؛ i <b ؛ i ++) {getMaxSort (0 ، i ، array ، childstrings) ؛ } StringBuffer SB = new StringBuffer () ؛ لـ (childstring s: childstrings) {sb.append (s2.SubString (S.MaxStart ، S.MaxStart + S.MaxLength)) ؛ sb.append ("/n") ؛ } return sb.toString () ؛ } // ابحث عن سلسلة العوامل المشتركة على void private getMaxSort (int i ، int j ، boolean [] [] ، قائمة <HividString> sortbean) {int length = 0 ؛ int start = j ؛ لـ (؛ i <a && j <b ؛ i ++ ، j ++) {if (array [i] [j]) {length ++ ؛ } آخر {// إضافة مباشرة ، حفظ جميع السلاسل الفرعية ، سيؤدي الحكم التالي إلى توفير أكبر سوط حالي //sortbean.add(new childstring (الطول ، البدء)) ؛ if (length == maxLength) {sortbean.add (New ChildString (length ، start)) ؛ } if if (length> maxLength) {sortbean.clear () ؛ MaxLength = الطول ؛ SortBean.Add (New Childstring (الطول ، البدء)) ؛ } الطول = 0 ؛ ابدأ = j + 1 ؛ } if (i == a-1 || j == b-1) {// إضافة مباشرة ، حفظ جميع السلاسل الفرعية ، فإن الحكم التالي يوفر فقط أكبر سوط حالي //sortbean.add(new childstring (الطول ، البدء)) ؛ if (length == maxLength) {sortbean.add (New ChildString (length ، start)) ؛ } if if (length> 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 * / public static void main (string [] args) {// todo method method method system.out.println (new StringCompare (). }} شكرا لك على القراءة ، آمل أن تساعدك. شكرا لك على دعمك لهذا الموقع!