ABC141-E Who Says a Pun?

問題へのリンク

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("5");
            WillReturn.Add("ababa");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2");
            WillReturn.Add("xy");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("13");
            WillReturn.Add("strangeorange");
            //5
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];
        int UB = S.Length - 1;

        // 最大長さ[StaInd1,StaInd2] なDP表
        int[,] DPArr = new int[UB + 1, UB + 1];

        for (int I = UB; 0 <= I; I--) {
            for (int J = UB; 0 <= J; J--) {
                if (S[I] != S[J]) {
                    DPArr[I, J] = 0;
                }
                else {
                    int FromI = I + 1;
                    int FromJ = J + 1;
                    int FromVal = 0;
                    if (FromI <= UB && FromJ <= UB) {
                        FromVal = DPArr[FromI, FromJ];
                    }
                    DPArr[I, J] = 1 + FromVal;
                }
            }
        }

        int Answer = 0;
        for (int I = 0; I <= UB; I++) {
            for (int J = 0; J <= UB; J++) {
                int AnswerKouho = Math.Min(DPArr[I, J], J - I);
                Answer = Math.Max(Answer, AnswerKouho);
            }
        }
        Console.WriteLine(Answer);
    }
}

解説

最大の長さ[開始添字1 , 開始添字2] の表を
不一致なら、0
一致したら、1 + 右下の値
として、右下から埋めます。

  a b a b a
a 5 0 3 0 1
b 0 4 0 2 0
a 3 0 3 0 1
b 0 2 0 2 0
a 1 0 1 0 1

そして、
min( DP表の値 , I - J)
の最大値が解になります。