cflib は plugins プロジェクトから，Stigmata直下のプロジェクトに移行したため，このリポジトリからは削除した．

[stigmata/stigmata-plugins.git] / osb / src / main / java / jp / sourceforge / stigmata / birthmarks / osb / LCSCalculator.java

diff --git a/osb/src/main/java/jp/sourceforge/stigmata/birthmarks/osb/LCSCalculator.java b/osb/src/main/java/jp/sourceforge/stigmata/birthmarks/osb/LCSCalculator.java
new file mode 100644 (file)
index 0000000..f46770f
--- /dev/null
+++ b/osb/src/main/java/jp/sourceforge/stigmata/birthmarks/osb/LCSCalculator.java
@@ -0,0 +1,59 @@
+package jp.sourceforge.stigmata.birthmarks.osb;\r
+\r
+/**\r
+ * LCS (Longest Common Subsequence; 最長共通部分列)の計算機．\r
+ * 与えられた型 T の配列2つから最長共通部分列を見つけ，長さを返す．\r
+ * \r
+ * @author Haruaki Tamada\r
+ */\r
+public class LCSCalculator<T>{\r
+    /**\r
+     * elementA と elementB の最長共通部分列の長さを返す．\r
+     * 配列の要素はnullを許容する．両方の要素がnullの場合は一致するとみなし，\r
+     * 片一方の要素のみがnullの場合は，一致しないとする．\r
+     * @param elementA 最長共通部分列の長さを計算する集合1\r
+     * @param elementB \r
+     * @return 最長共通部分列の長さ\r
+     * @exception NullPointerException 与えらえた配列のどちらか，もしくは両方が null の場合．\r
+     */\r
+    public int calculate(T[] elementA, T[] elementB){\r
+        if(elementA == null || elementB == null){\r
+            throw new NullPointerException();\r
+        }\r
+        int[][] table = new int[elementA.length + 1][elementB.length + 1];\r
+        for(int i = 0; i <= elementA.length; i++){\r
+            for(int j = 0; j <= elementB.length; j++){\r
+                if(i == 0 || j == 0){\r
+                    table[i][j] = 0;\r
+                }\r
+                else if((elementA[i - 1] == null && elementB[j - 1] == null) ||\r
+                        elementA[i - 1] != null && elementA[i - 1].equals(elementB[j - 1])){\r
+                    table[i][j] = max(table[i - 1][j - 1] + 1, table[i - 1][j], table[i][j - 1]);\r
+                }\r
+                else{\r
+                    table[i][j] = max(table[i - 1][j - 1], table[i - 1][j], table[i][j - 1]);\r
+                }\r
+            }\r
+        }\r
+        return table[elementA.length][elementB.length];\r
+    }\r
+\r
+    /**\r
+     * 与えられた3つの整数値のうち，一番大きな値を返す．\r
+     * 全て正の数が与えらえるものとする．\r
+     */\r
+    private int max(int value1, int value2, int value3){\r
+        assert value1 >= 0;\r
+        assert value2 >= 0;\r
+        assert value3 >= 0;\r
+\r
+        int max = value1;\r
+        if(max < value2){\r
+            max = value2;\r
+        }\r
+        if(max < value3){\r
+            max = value3;\r
+        }\r
+        return max;\r
+    }\r
+}\r