Java implementa a correspondência de strings para encontrar a substring comum máxima de duas strings

Este artigo descreve o método de Java para encontrar a maior substring comum de duas cordas. Compartilhe -o para sua referência, como segue:

Recentemente, tenho um requisito para comparação de texto no meu trabalho de projeto. Depois de estudar esse período, resumi o conteúdo deste blog: encontre a maior substring comum de duas cordas.

Idéia do algoritmo: calcule a substring comum de duas seqüências baseadas em gráficos. Para idéias específicas de algoritmo, consulte a figura a seguir:

String de entrada S1: string de entrada achmacmh s2: macham

1. A etapa A é dividir os bytes S1 e S2 de Strings, respectivamente, para formar uma matriz bidimensional;
2. Os valores na matriz bidimensional são mostrados em b. Por exemplo, os valores na primeira linha e a primeira coluna representam se os primeiros bytes das cadeias S2 e S1 são iguais. Se forem iguais, é 1, caso contrário, é 0 e, finalmente, a matriz bidimensional mostrada em B é gerada;
3. Encontre o fator comum na linha diagonal em uma matriz bidimensional (a linha diagonal é o valor do canto inferior direito do elemento A, ou seja, o próximo elemento de a [i] [j] é um [i+1] [j+1]; o fator comum é uma corda composta da posição onde 1 está);
4. Classifique todos os fatores comuns, retornando o valor do maior fator comum.

O código de implementação específico é o seguinte:

 pacote cn.lulei.compare; importar java.util.arraylist; importar java.util.Collections; importar java.util.comparator; importar java.util.list; classe pública stringcompare {private int a; privado int b; public String getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // O comprimento S1 faz da linha b = s2.Length (); // Defina a coluna do comprimento s2 if (a == 0 || b == 0) {return ""; } // Defina a matriz correspondente booleana [] [] Array = new boolean [a] [b]; for (int i = 0; i <a; i ++) {char c1 = s1.charat (i); for (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}}} // Encontre todas as seqüências de caracteres comuns, salve as informações como a posição inicial e o comprimento em relação à segunda lista de string <fridString> ChildStrings = new ArrayList <fridString> (); para (int i = 0; i <a; i ++) {getMaxSort (i, 0, matriz, childstrings); } para (int i = 1; i <b; i ++) {getMaxSort (0, i, array, childstrings); } // classificação de classificação (ChildStrings); if (ChildStrings.size () <1) {return ""; } // retorna a sequência de fator comum máxima int max = childstrings.get (0) .maxLength; StringBuffer sb = new StringBuffer (); para (ChildString s: ChildStrings) {if (max! = s.maxLength) {break; } sb.append (s2.substring (s.maxstart, s.maxstart + s.maxLength)); sb.append ("/n"); } return sb.toString (); } // Classificação, Flashback private void Sort (list <fridString> list) {collectionS.sort (list, novo comparador <fridString> () {public int compare (ChildString O1, ChildString o2) {retorna o2.Maxlength - o1.MaxLength;}}); } // Encontre a sequência de fatores comuns em uma barra de vazio privado getMaxSort (int i, int j, boolean [] [] matriz, list <fridString> sortBean) {int length = 0; int start = j; para (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {length ++; } else {sortBean.add (new ChildString (comprimento, start)); comprimento = 0; start = j + 1; } if (i == a-1 || j == b-1) {sorTBean.add (novo ChildString (comprimento, start)); }}} // classe pública Classe 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 Método Auto-Generado Stub System.out.println (new StringCompare (). getMaxLengthCommonstring ("achmacmh", "macham"); }}

O resultado final da execução do programa é:

Para comparação dos dois arquivos, acho que essa idéia algorítmica pode ser referida (e agora e para implementação), que será escrita em um futuro blog.

No processo de implementação acima, todas as informações comuns da substring são salvas com uma matriz e, em seguida, a maior substring é classificada. Se esse método é apenas para encontrar a maior substring, o algoritmo não é muito razoável. Portanto, as seguintes modificações são feitas. A lista salva apenas a maior substring no cálculo atual. A implementação específica é a seguinte:

 / ***@Descrição: Comparação de String*/ Package com.lulei.test; importar java.util.arraylist; importar java.util.list; classe pública stringcompare {private int a; privado int b; private int maxlength = -1; public String getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // O comprimento S1 é usado para fazer a linha b = s2.length (); // o comprimento S2 é usado para fazer a coluna se (a == 0 || b == 0) {return ""; } // Defina a matriz correspondente booleana [] [] Array = new boolean [a] [b]; for (int i = 0; i <a; i ++) {char c1 = s1.charat (i); for (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}} // Termine todas as seqüências de caracteres comuns e salve as informações como a posição inicial e o comprimento em relação à Segunda String List <fridString> ChildStrings = new ArrayList <fridString> (); para (int i = 0; i <a; i ++) {getMaxSort (i, 0, matriz, childstrings); } para (int i = 1; i <b; i ++) {getMaxSort (0, i, array, childstrings); } StringBuffer sb = new StringBuffer (); para (ChildString s: ChildStrings) {sb.append (s2.substring (s.maxstart, s.maxstart + s.maxlength)); sb.append ("/n"); } return sb.toString (); } // Encontre a sequência de fatores comuns em uma barra de vazio privado getMaxSort (int i, int j, boolean [] [] matriz, list <fridString> sortBean) {int length = 0; int start = j; para (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {length ++; } else {// Adicionar diretamente, salve todas as substringas, o julgamento a seguir salvará apenas a maior substring atual //sortbean.add(new ChildString (comprimento, start)); if (comprimento == maxLength) {sortBean.add (new ChildString (comprimento, start)); } else if (comprimento> maxLength) {sortBean.clear (); maxLength = comprimento; sortBean.add (novo ChildString (comprimento, start)); } comprimento = 0; start = j + 1; } if (i == a-1 || j == b-1) {// Adicionar diretamente, salve todas as substringas, o julgamento a seguir apenas salva a maior substring atual //sortbean.add(New ChildString (comprimento, start)); if (comprimento == maxLength) {sortBean.add (new ChildString (comprimento, start)); } else if (comprimento> maxLength) {sortBean.clear (); maxLength = comprimento; sortBean.add (novo ChildString (comprimento, start)); }}}}} // classe pública Classe 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 Método Auto-Generado Stub System.out.println (new StringCompare (). getMaxLengthCommonstring ("abcdef", "defabc"); }}

Obrigado pela leitura, espero que isso possa ajudá -lo. Obrigado pelo seu apoio a este site!