Educational DP Contest F 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("axyb");
            WillReturn.Add("abyxb");
            //axb
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("aa");
            WillReturn.Add("xayaz");
            //aa
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("a");
            WillReturn.Add("z");
            //
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("abracadabra");
            WillReturn.Add("avadakedavra");
            //aaadara
        }
        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(DeriveLCS(S, T));
    }

    // 文字列2つを引数として、LCSを求める
    static string DeriveLCS(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 Val1 = GetFunc(X - 1, Y);
                    int Val2 = GetFunc(X, Y - 1);

                    if (Val1 < Val2) {
                        BanArr[X, Y] = Val2;
                    }
                    else {
                        BanArr[X, Y] = Val1;
                    }
                }
            }
        }

        int LCSLen = BanArr[UB_X, UB_Y];
        int XInd = UB_X;
        int YInd = UB_Y;
        var sb = new System.Text.StringBuilder();
        while (LCSLen > 0) {
            // 一致したら左上に移動する
            if (pStr1[XInd] == pStr2[YInd]) {
                sb.Insert(0, pStr1[XInd]);
                XInd--;
                YInd--;
                LCSLen--;
            }

            // 一致しなかったら、減らないほうに移動する
            else if (XInd > 0 && BanArr[XInd, YInd] == BanArr[XInd - 1, YInd]) {
                XInd--;
            }
            else {
                YInd--;
            }
        }
        return sb.ToString();
    }
}

解説

まずDPでLCSの長さを求め、

2次元配列の右下から、
文字が一致したら左上に移動する。
一致しなかったら、LCSの長さが減らないほうに移動する。
というアルゴリズムでLCSの文字列を求めてます。

類題

ALDS1_10_C: Longest Common Subsequence