動的計画思想--最長の共通サブストリング

       NLP ML       ，        ，     ，           。
                   ，      （              ）

static void Main(string[] args)

        {

            int max = LcsLen(" q  ", "  q  ");

            Console.WriteLine(max);

            Console.ReadLine();

        }

        static int LcsLen(String s1, String s2)

        {

            int[,] lenLCS = new int[s1.Length + 1, s2.Length + 1];



            for (int i = 1; i <= s1.Length; i++)

                for (int j = 1; j <= s2.Length; j++)

                    if (s1[i - 1] == s2[j - 1])

                        lenLCS[i, j] = 1 + lenLCS[i - 1, j - 1];

                    else

                        lenLCS[i, j] = Math.Max(lenLCS[i - 1, j], lenLCS[i, j - 1]);



            return lenLCS[s1.Length, s2.Length];

        }

public static void main(String[] args) {

        int max=lcsLen("      ","       ");

        System.out.println(max);

    }

    

    private static int lcsLen(String s1,String s2){

        int[][] lenLCS=new int[s1.length()+1][s2.length()+1];

        for (int i = 1; i <= s1.length(); i++)

            for (int j = 1; j <= s2.length(); j++)

                if(s1.charAt(i-1)==s2.charAt(j-1))

                    lenLCS[i][j]=1+lenLCS[i-1][j-1];

                else

                    lenLCS[i][j]=Math.max(lenLCS[i-1][j], lenLCS[i][j-1]);

        int max=lenLCS[s1.length()][s2.length()];

        return max;

    }