この記事では、2つの文字列の最大の一般的なサブストリングを見つけるためのJavaの方法について説明します。次のように、参照のために共有してください。
最近、プロジェクト作業でテキスト比較の要件があります。この期間を研究した後、このブログの内容を要約しました。2つの文字列の最大の一般的なサブストリングを見つけます。
アルゴリズムのアイデア：グラフに基づいて2つの文字列の共通のサブストリングを計算します。特定のアルゴリズムのアイデアについては、次の図を参照してください。
入力文字列S1：ACHMACMH入力文字列S2：MACHAM
特定の実装コードは次のとおりです。
パッケージcn.lulei.compare; java.util.arraylistをインポートします。 java.util.collectionsをインポートします。 java.util.comparatorをインポートします。 java.util.listをインポートします。 public class stringcompare {private int a;プライベートINT B; public String getMaxLengthCommonstring（String S1、String 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]を設定します。 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; }}}} //すべての共通要因文字列を見つけ、2番目の文字列リスト<Childring> Childring> childring = new ArrayList <ChuldString>（）に比べて、情報を開始位置と長さとして保存します。 for（int i = 0; i <a; i ++）{getMaxsort（i、0、array、Childrings）; } for（int i = 1; i <b; i ++）{getMaxsort（0、i、array、Childrings）; } // sort（shildstrings）; if（childstrings.size（）<1）{return ""; } //最大共通因子文字列int max = childring.get（0）.maxlengthを返します。 stringbuffer sb = new StringBuffer（）; for（childstring s：childrings）{if（max！= s.maxlength）{break; } sb.append（s2.substring（s.maxstart、s.maxstart + s.maxlength））; sb.append（ "/n"）; } return sb.toString（）; } //ソート、フラッシュバックプライベートボイドソート（リスト<ChildString>リスト）{collections.sort（list、new Comparator <ChildString>（）{public int Compare（CherdString O1、CherdString O2）{return O2.maxLength -O1.MaxLength;}}）; } //スラッシュprivate void getmaxsort（int i、int j、boolean [] [] array、list <Chuldstring> sortbean）{int length = 0; int start = j; for（; i <a && j <b; i ++、j ++）{if（array [i] [j]）{length ++; } else {sortbean.add（new Childstring（length、start））;長さ= 0; start = j + 1; } if（i == a-1 || j == b-1）{sortbean.add（new Childstring（length、start））; }}} //パブリックファクタークラス子育て{int maxlength; int maxstart; Childstring（int maxlength、int maxstart）{this.maxlength = maxlength; this.maxstart = maxstart; }} / ** * @param args * / public static void main（string [] args）{// todo auto-fenated method stub system.out.println（new StringCompare（）。 }}プログラムの最終的な実行結果は次のとおりです。
2つのファイルを比較するために、私は個人的に、このアルゴリズムのアイデアは、今後のブログで書かれているものを参照できると考えています。
上記の実装プロセスでは、すべての一般的なサブストリング情報が配列で保存され、最大のサブストリングがソートされます。この方法が最大のサブストリングを見つけるためだけの場合、アルゴリズムはあまり合理的ではありません。したがって、次の変更が行われます。リストは、現在の計算で最大のサブストリングのみを保存します。特定の実装は次のとおりです。
/ ***@説明：文字列比較*/パッケージcom.lulei.test; java.util.arraylistをインポートします。 java.util.listをインポートします。 public class stringcompare {private int a;プライベートINT B; private int maxlength = -1; public String getMaxLengthCommonstring（String S1、String S2）{if（S1 == null || s2 == null）{return null; } a = s1.length（）; // s1の長さは、row b = s2.length（）; // s2の長さを作成するために使用されます（a == 0 || b == 0）{return ""; } //一致するマトリックスBoolean [] [] 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; }}} //すべての共通要因文字列を完了し、2番目の文字列リスト<Childring> Childring> childring = new ArrayList <ChuldString>（）に比べて、情報を開始位置と長さとして保存します。 for（int i = 0; i <a; i ++）{getMaxsort（i、0、array、Childrings）; } for（int i = 1; i <b; i ++）{getMaxsort（0、i、array、Childrings）; } stringbuffer sb = new StringBuffer（）; for（childstring s：childstrings）{sb.append（s2.substring（s.maxstart、s.maxstart + s.maxlength））; sb.append（ "/n"）; } return sb.toString（）; } //スラッシュprivate void getmaxsort（int i、int j、boolean [] [] array、list <Chuldstring> sortbean）{int length = 0; int start = j; for（; i <a && j <b; i ++、j ++）{if（array [i] [j]）{length ++; } else {//すべてのサブストリングを直接追加して保存すると、次の判断は現在の最大のサブストリング//sortbean.add（New ChildString（length、start））のみを保存します。 if（length == maxlength）{sortbean.add（new Childstring（length、start））; } else if（length> maxlength）{sortbean.clear（）; maxlength = length; sortbean.add（new Childstring（length、start））; } length = 0; start = j + 1; } if（i == a-1 || j == b-1）{//すべてのサブストリングを直接追加して保存します。次の判断は、現在の最大のサブストリング//sortbean.add（new childstring（length、start）のみを保存します。 if（length == maxlength）{sortbean.add（new Childstring（length、start））; } else if（length> maxlength）{sortbean.clear（）; maxlength = length; sortbean.add（new Childstring（length、start））; }}}}} //パブリックファクタークラス子育て{int maxlength; int maxstart; Childstring（int maxlength、int maxstart）{this.maxlength = maxlength; this.maxstart = maxstart; }} / ** * @param args * / public static void main（string [] args）{// todo auto-fenated method stub.out.println（new StringCompare（）。 }}読んでくれてありがとう、私はそれがあなたを助けることができることを願っています。このサイトへのご支援ありがとうございます！