A20 LCS

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("mynavi");
            WillReturn.Add("monday");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("tokyo");
            WillReturn.Add("kyoto");
            //3
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[0];
        string T = InputList[1];
        Console.WriteLine(DeriveLCSLength(S, T));
    }

    static int DeriveLCSLength(string pStr1, string pStr2)
    {
        int UB_X = pStr1.Length - 1;
        int UB_Y = pStr2.Length - 1;

        int[,] BanArr = new int[UB_X + 1, UB_Y + 1];

        // 範囲外なら0、範囲外でなければ、配列の値を返す
        Func<int, int, int> GetFunc = (pX, pY) =>
        {
            if (pX < 0 || pY < 0) return 0;
            return BanArr[pX, pY];
        };

        for (int X = 0; X <= UB_X; X++) {
            for (int Y = 0; Y <= UB_Y; Y++) {

                // 一致したら左上の値+1
                if (pStr1[X] == pStr2[Y]) {
                    BanArr[X, Y] = GetFunc(X - 1, Y - 1) + 1;
                }
                else { // 不一致なら、左と上での最大値
                    int MaxVal = Math.Max(GetFunc(X - 1, Y), GetFunc(X, Y - 1));
                    BanArr[X, Y] = MaxVal;
                }
            }
        }
        return BanArr[UB_X, UB_Y];
    }
}

解説

LCSの長さは、DPで求めることができます。