AOJ 0528 共通部分文字列

問題へのリンク

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("ABRACADABRA");
            WillReturn.Add("ECADADABRBCRDARA");
            WillReturn.Add("UPWJCIRUCAXIIRGL");
            WillReturn.Add("SBQNYBSBZDFNEV");
            //5
            //0
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        for (int I = 0; I <= InputList.Count - 1; I += 2) {
            string S = InputList[I];
            string T = InputList[I + 1];
            short Answer = DeriveLCSLength(S, T);
            Console.WriteLine(Answer);
        }
    }

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

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

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

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

                // 一致したら左上の値+1
                if (pStr1[X] == pStr2[Y]) {
                    BanArr[X, Y] = (short)(GetFunc((short)(X - 1), (short)(Y - 1)) + (short)1);
                    Answer = Math.Max(Answer, BanArr[X, Y]);
                }
                else { // 不一致なら、0
                    BanArr[X, Y] = 0;
                }
            }
        }
        return Answer;
    }
}

解説

最長共通部分文字列の長さ[文字列1をどこまで見たか , 文字列2をどこまで見たか]
をDPで更新してます。

MLE対策で、int型でなくshort型を使用してます。