第11回PAST L だいたい最長共通部分列

問題へのリンク

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("strength");
            WillReturn.Add("slang");
            WillReturn.Add("1");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("asdbvaklwebjkalhakslhgweqwbq");
            WillReturn.Add("obqweogkmawgjkoanboebeoqejkazxcnmvqse");
            WillReturn.Add("10");
            //19
        }
        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];
        int K = int.Parse(InputList[2]);

        int UB_X = S.Length - 1;
        int UB_Y = T.Length - 1;
        int UB_K = K;

        // 最長の長さ[文字列1をどこまで見たか , 文字列2をどこまで見たか , 不一致な文字の数]
        int?[, ,] BanArr = new int?[UB_X + 1, UB_Y + 1, UB_K + 1];

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            if (S[LoopX] == T[0]) {
                BanArr[LoopX, 0, 0] = 1;
            }
            else {
                BanArr[LoopX, 0, 1] = 1;
            }
        }

        for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
            if (S[0] == T[LoopY]) {
                BanArr[0, LoopY, 0] = 1;
            }
            else {
                BanArr[0, LoopY, 1] = 1;
            }
        }

        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopK = 0; LoopK <= UB_K; LoopK++) {
                    if (BanArr[LoopX, LoopY, LoopK].HasValue == false) continue;

                    Action<int, int, int, int> SendAct = (pNewX, pNewY, pNewK, pNewVal) =>
                    {
                        if (UB_X < pNewX) return;
                        if (UB_Y < pNewY) return;
                        if (UB_K < pNewK) return;

                        if (BanArr[pNewX, pNewY, pNewK].HasValue) {
                            if (BanArr[pNewX, pNewY, pNewK] >= pNewVal) {
                                return;
                            }
                        }
                        BanArr[pNewX, pNewY, pNewK] = pNewVal;
                    };

                    int CurrVal = BanArr[LoopX, LoopY, LoopK].Value;

                    // 右に配る
                    SendAct(LoopX + 1, LoopY, LoopK, CurrVal);

                    // 下に配る
                    SendAct(LoopX, LoopY + 1, LoopK, CurrVal);

                    // 右下に配る
                    int NewX = LoopX + 1;
                    int NewY = LoopY + 1;
                    if (NewX <= UB_X && NewY <= UB_Y) {
                        if (S[NewX] == T[NewY]) {
                            SendAct(LoopX + 1, LoopY + 1, LoopK, CurrVal + 1);
                        }
                        else {
                            SendAct(LoopX + 1, LoopY + 1, LoopK + 1, CurrVal + 1);
                        }
                    }
                }
            }
        }

        var AnswerKouhoList = new List<int>();
        for (int LoopX = 0; LoopX <= UB_X; LoopX++) {
            for (int LoopY = 0; LoopY <= UB_Y; LoopY++) {
                for (int LoopK = 0; LoopK <= UB_K; LoopK++) {
                    if (BanArr[LoopX, LoopY, LoopK].HasValue) {
                        AnswerKouhoList.Add(BanArr[LoopX, LoopY, LoopK].Value);
                    }
                }
            }
        }
        Console.WriteLine(AnswerKouhoList.Max());
    }
}

解説

LCSの長さを求める有名アルゴリズムがあります。
ALDS1_10_C: Longest Common Subsequence

応用して、
最長の長さ[文字列1をどこまで見たか , 文字列2をどこまで見たか , 不一致な文字の数]
を状態に持つ、配るDPで解いてます。