この記事では、Javaアルゴリズムの最も長い一般的なサブシーケンス問題（LCS）について説明します。次のように、参照のために共有してください。
問題の説明：特定のシーケンスのサブシーケンスは、いくつかの要素がシーケンスから削除された後に得られるシーケンスです。正確に言うと、シーケンスx = {x1、x2、…、xm}が与えられた場合、別のシーケンスz = {z1、z2、…、zk}は、xのサブシッケンスであり、厳密に漸進的な添え字シーケンス{i1、i2、…、ik}の存在を指します。たとえば、シーケンスz = {b、c、d、b}は、シーケンスx = {a、b、c、b、d、a、b}のサブシーケンスであり、対応する増分サブスクリプト配列は{2,3,5,7}です。 2つのシーケンスxとyが与えられた場合、他のシーケンスzがxとyの両方のシーケンスである場合、zはシーケンスxとyの共通サブシーケンスと呼ばれます。たとえば、x = {a、b、c、b、d、a、b}および{b、d、c、a、b、a a}はxとyの一般的なサブシーケンスでもあります。さらに、後者はxとyの最も長い一般的なサブシーケンスの1つです。これは、xとyが4を超える共通サブシーケンスを持たないため、2つのシーケンスx = {x1、x2、…、xm}とy = {y1、y2、…、yn}を考えると、xの1つを見つける必要があります。
問題分析：x = {a、b、c、b、d、a、b}、y = {b、c、a、b、a} xとyの最も長い一般的なサブシーケンスを見つける最も簡単な方法は、網羅的な方法です。 Xの複数のサブシーケンスについては、それがyのサブシーケンスであるかどうかを確認し、それによってそれがxとyの一般的なサブシーケンスであるかどうかを決定します。セットの特性からのセットから、Mを持つセットには合計2^mの異なるサブシーケンスが必要なため、徹底的な方法に指数操作時間が必要です。問題の特性をさらに分解すると、最長の一般的なサブシーケンス問題には、実際に最適な下部構造特性があります。
シーケンスx = {x1、x2、... xm}およびy = {y1、y2、... yn}のシーケンスx = {x1、x2、... xm}の最長サブシーケンスがz = {z1、z2、... zk}であるとします。それからあります：
（1）xm = ynの場合、zk = xm = yn、zk-1はxm-1およびyn-1の最も長い一般的なサブシーケンスです。
（2）xm！= ynおよびzk！= xmの場合、zはxm-1およびyの最長の共通サブシーケンスです。
（3）xm！= ynおよびzk！= ynの場合、zはxとyn-1の最も長い一般的なサブシーケンスです。
ここで、xm-1 = {x1、x2…xm-1}、yn-1 = {y1、y2…yn-1}、zk-1 = {z1、z2…zk-1}。
再帰関係：c [i] [j]を使用して、シーケンスxiおよびyjの最も長い一般的なサブシーケンスの長さを記録します。ここで、xi = {x1、x2…xi}、yj = {y1、y2…yj}。 i = 0またはj = 0の場合、空のシーケンスはXiおよびYJの最も長い一般的なサブシーケンスです。この時点で、c [i] [j] = 0; i、j> 0、xi = yj、c [i] [j] = c [i-1] [j-1] +1;私、j> 0、xi！= yj、
c [i] [j] = max {c [i] [j-1]、c [i-1] [j]}、それによって再帰的な関係を次のように確立します。
最適なソリューションを構築する：上記の分析から、x = {x1、x2、... xm}およびy = {y1、y2、... yn}の最も長い一般的なサブシーケンスを見つけるために、次の方法で再帰的に実行できます。 Y. Xm！= Ynの場合、2つのサブ問題を解決する必要があります。つまり、XM-1とYの最も長い一般的なサブシーケンスの1つ、およびXおよびYN-1の最も長い一般的なサブシーケンスの1つを見つける必要があります。これらの2つの一般的なサブシーケンスの長いことは、xとyの最も長い一般的なサブシーケンスです。アレイb [i] [j]が、サブ問題が得られるc [i] [j]の値を記録するとします。 B [M] [n]から始めて、その値に応じて配列Bで検索します。 b [i] [j] = 1の場合、xiとyjの最も長い一般的なサブシーケンスは、xi-1とyj-1のテールにxiを追加することによって得られるサブシーケンスです。 b [i] [j] = 2の場合、xiとyjの最も長い一般的なサブシーケンスは、xi-1とyj-1の最も長い一般的なサブシーケンスと同じであることを意味します。 b [i] [j] = 3の場合、xiとyjの最も長い一般的なサブシーケンスは、xiおよびyj-1の最も長い一般的なサブシーケンスと同じです。
コードは次のとおりです。
パッケージlcs; public class lcs {public static int [] [] lcslength（string [] x、string [] y）{int m = x.length; int n = y.length; int [] [] b = new int [x.length] [y.length]; int [] [] c = new int [x.length] [y.length]; for（int i = 1; i <m; i ++）{c [i] [0] = 0; } for（int i = 1; i <n; i ++）{c [0] [i] = 0; } for（int i = 1; i <m; i ++）{for（int j = 1; j <n; j ++）{if（x [i] == y [j]）{c [i] [j] = c [i-1] [j-1]+1; b [i] [j] = 1; } else if（c [i-1] [j]> = c [i] [j-1]）{c [i] [j] = c [i-1] [j]; b [i] [j] = 2; } else {c [i] [j] = c [i] [j-1]; b [i] [j] = 3; }}} return b; } public static void lcs（int [] [] b、string [] x、int i、int j）{if（i == 0 || j == 0）return; if（b [i] [j] == 1）{lcs（b、x、i -1、j -1）; System.out.print（x [i] + ""）; } else if（b [i] [j] == 2）{lcs（b、x、i -1、j）; } else lcs（b、x、i、j-1）; } public static void main（string args []）{system.out.println（ "wulin.comテスト結果："）; string [] x = {"" "、" a "、" b "、" c "、" b "、" d "、" a "、" b "}; string [] y = {""、 "b"、 "d"、 "c"、 "a"、 "b"、 "a"}; int [] [] b = lcslength（x、y）; system.out.println（ "xとyの最も長い共通サブシーケンスは次のとおりです。"）; lcs（b、x、x.length -1、y.length -1）; }}実行結果：
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。