Java mengimplementasikan pencocokan string untuk menemukan substring umum maksimum dari dua string

Artikel ini menjelaskan metode Java untuk menemukan substring umum terbesar dari dua string. Bagikan untuk referensi Anda, sebagai berikut:

Baru -baru ini, saya memiliki persyaratan untuk perbandingan teks dalam pekerjaan proyek saya. Setelah mempelajari periode waktu ini, saya telah merangkum konten blog ini: temukan substring umum terbesar dari dua string.

Ide Algoritma: Hitung substring umum dari dua string berdasarkan grafik. Untuk ide algoritma tertentu, silakan merujuk ke gambar berikut:

Input String S1: ACHMACMH Input String S2: Macham

1. Langkah A adalah untuk membagi string S1 dan S2 byte masing-masing untuk membentuk array dua dimensi;
2. Nilai-nilai dalam array dua dimensi ditunjukkan pada b. Misalnya, nilai -nilai di baris pertama dan kolom pertama mewakili apakah byte pertama dari string S2 dan S1 sama. Jika mereka sama, itu adalah 1, jika tidak 0, dan akhirnya array dua dimensi yang ditunjukkan pada B dihasilkan;
3. Temukan faktor umum pada garis diagonal dalam array dua dimensi (garis diagonal adalah nilai sudut kanan bawah elemen A, yaitu elemen berikutnya dari [i] [j] adalah [i+1] [j+1]; faktor umum adalah string yang terdiri dari posisi di mana 1 adalah);
4. Urutkan semua faktor umum, mengembalikan nilai faktor umum terbesar.

Kode implementasi spesifik adalah sebagai berikut:

 paket cn.lulei.compare; impor java.util.arraylist; impor java.util.collections; impor java.util.comparator; impor java.util.list; kelas publik StringCompare {private int a; int b private; String publik getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // panjang s1 membuat baris b = s2.length (); // atur kolom panjang s2 jika (a == 0 || b == 0) {return ""; } // atur matriks pencocokan boolean [] [] array = boolean baru [a] [b]; untuk (int i = 0; i <a; i ++) {char c1 = s1.charat (i); untuk (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}}} // Temukan semua string faktor umum, simpan informasi sebagai posisi awal dan panjang relatif terhadap daftar string kedua <ShildString> childStrings = new ArrayList <ShildString> (); untuk (int i = 0; i <a; i ++) {getmaxsort (i, 0, array, childstrings); } untuk (int i = 1; i <b; i ++) {getmaxsort (0, i, array, childstrings); } // sortir (childstrings); if (childstrings.size () <1) {return ""; } // Kembalikan string faktor umum maksimum int int max = childstrings.get (0) .maxlength; StringBuffer SB = StringBuffer baru (); untuk (childString s: childStrings) {if (max! = s.maxlength) {break; } SB.Append (s2.substring (s.maxstart, s.maxstart + s.maxlength)); SB.Append ("/n"); } return sb.toString (); } // penyortiran, flashback private void sort (Daftar <N ChildString> Daftar) {collections.sort (daftar, pembanding baru <ShildString> () {public int perbandingan (ChildString O1, ChildString O2) {return o2.maxlength - o1.maxlength;}}); } // Temukan string faktor umum pada slash private void getMaxsort (int i, int j, boolean [] [] array, daftar <ChildString> sortbean) {int length = 0; int start = j; untuk (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {length ++; } else {sortbean.add (childString baru (panjang, mulai)); panjang = 0; mulai = j + 1; } if (i == a-1 || j == b-1) {sortbean.add (childString baru (panjang, mulai)); }}} // Class Public Factor 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 Metode yang dihasilkan secara otomatis System.out.println (stringCompare baru (). GetMaxLengthCommonstring ("ACHMACMH", "Macham")); }}

Hasil eksekusi akhir dari program ini adalah:

Sebagai perbandingan dari kedua file tersebut, saya pribadi berpikir bahwa ide algoritmik ini dapat dirujuk (dan sekarang dan untuk implementasi), yang akan ditulis dalam blog mendatang.

Dalam proses implementasi di atas, semua informasi substring umum disimpan dengan array, dan kemudian substring terbesar diurutkan. Jika metode ini hanya untuk menemukan substring terbesar, algoritma ini tidak terlalu masuk akal. Oleh karena itu, modifikasi berikut dibuat. Daftar hanya menyimpan substring terbesar dalam perhitungan saat ini. Implementasi spesifik adalah sebagai berikut:

 / ***@Deskripsi: Perbandingan String*/ Paket com.lulei.test; impor java.util.arraylist; impor java.util.list; kelas publik StringCompare {private int a; int b private; private int maxlength = -1; String publik getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // panjang s1 digunakan untuk membuat baris b = s2.length (); // panjang s2 digunakan untuk membuat kolom jika (a == 0 || b == 0) {return ""; } // atur matriks pencocokan boolean [] [] array = boolean baru [a] [b]; untuk (int i = 0; i <a; i ++) {char c1 = s1.charat (i); untuk (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}} // Selesaikan semua string faktor umum dan simpan informasi sebagai posisi awal dan panjang relatif terhadap daftar string kedua <ShildString> childStrings = new ArrayList <ChildString> (); untuk (int i = 0; i <a; i ++) {getmaxsort (i, 0, array, childstrings); } untuk (int i = 1; i <b; i ++) {getmaxsort (0, i, array, childstrings); } StringBuffer SB = StringBuffer baru (); untuk (ChildString S: ChildStrings) {SB.Append (S2.substring (s.maxstart, s.maxstart + s.maxlength)); SB.Append ("/n"); } return sb.toString (); } // Temukan string faktor umum pada slash private void getMaxsort (int i, int j, boolean [] [] array, daftar <ChildString> sortbean) {int length = 0; int start = j; untuk (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {length ++; } else {// Langsung tambahkan, simpan semua substring, penilaian berikut hanya akan menyimpan substring terbesar saat ini //sortbean.add(new ChildString (length, start)); if (length == maxlength) {sortbean.add (childString baru (panjang, mulai)); } lain jika (panjang> maxlength) {sortbean.clear (); maxlength = panjang; sortbean.add (anak baru (panjang, mulai)); } panjang = 0; mulai = j + 1; } if (i == a-1 || j == b-1) {// Langsung tambahkan, simpan semua substring, penilaian berikut hanya menyimpan substring terbesar saat ini //sortbean.add(new Childstring (length, start)); if (length == maxlength) {sortbean.add (childString baru (panjang, mulai)); } lain jika (panjang> maxlength) {sortbean.clear (); maxlength = panjang; sortbean.add (anak baru (panjang, mulai)); }}}}} // Class Public Factor 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 Metode yang dihasilkan secara otomatis System.out.println (stringCompare baru (). GetMaxLengthCommonstring ("ABCDEF", "DEFABC")); }}

Terima kasih telah membaca, saya harap ini dapat membantu Anda. Terima kasih atas dukungan Anda untuk situs ini!