ABC324-E Joint Two Strings

問題へのリンク

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("3 bac");
            WillReturn.Add("abba");
            WillReturn.Add("bcb");
            WillReturn.Add("aaca");
            //3
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("5 xx");
            WillReturn.Add("x");
            WillReturn.Add("x");
            WillReturn.Add("x");
            WillReturn.Add("x");
            WillReturn.Add("x");
            //25
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1 y");
            WillReturn.Add("x");
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("10 ms");
            WillReturn.Add("mkgn");
            WillReturn.Add("m");
            WillReturn.Add("hlms");
            WillReturn.Add("vmsle");
            WillReturn.Add("mxsm");
            WillReturn.Add("nnzdhi");
            WillReturn.Add("umsavxlb");
            WillReturn.Add("ffnsybomr");
            WillReturn.Add("yvmm");
            WillReturn.Add("naouel");
            //68
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static string mT;

    struct StrInfoDef
    {
        internal int StaMatchCnt; // 先頭からの一致数
        internal int EndMatchCnt; // 末尾からの一致数
    }
    static List<StrInfoDef> mStrInfoList = new List<StrInfoDef>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        string[] SplitArr = InputList[0].Split(' ');
        mT = SplitArr[1];

        foreach (string EachStr in InputList.Skip(1)) {
            StrInfoDef WillAdd;
            WillAdd.StaMatchCnt = DeriveStaMatchCnt(EachStr);
            WillAdd.EndMatchCnt = DeriveEndMatchCnt(EachStr);
            mStrInfoList.Add(WillAdd);
            //Console.WriteLine("{0}のStaMatchCnt={1},EndMatchCnt={2}", 
            //    EachStr, WillAdd.StaMatchCnt, WillAdd.EndMatchCnt);
        }

        var ValList1 = new List<long>();
        var ValList2 = new List<long>();
        foreach (StrInfoDef EachStrInfo in mStrInfoList) {
            ValList1.Add(EachStrInfo.StaMatchCnt);
            ValList2.Add(EachStrInfo.EndMatchCnt);
        }

        ValList2.Sort();

        long Answer = 0;
        foreach (long EachInt in ValList1) {
            long RestCnt = mT.Length - EachInt;
            long ResultInd = ExecNibunhou_LowerBound(RestCnt, ValList2);
            if (ResultInd == -1) continue;

            long UB = ValList2.Count - 1;
            Answer += UB - ResultInd + 1;
        }
        Console.WriteLine(Answer);
    }

    // 先頭からの一致数を返す
    static int DeriveStaMatchCnt(string CurrStr)
    {
        int MatchCnt = 0;

        int UB1 = mT.Length - 1;
        int UB2 = CurrStr.Length - 1;

        int Ind1 = 0;
        int Ind2 = 0;
        while (Ind1 <= UB1 && Ind2 <= UB2) {
            if (mT[Ind1] == CurrStr[Ind2]) {
                Ind1++; Ind2++;
                MatchCnt++;
            }
            else {
                Ind2++;
            }
        }
        return MatchCnt;
    }

    // 末尾からの一致数を返す
    static int DeriveEndMatchCnt(string CurrStr)
    {
        int MatchCnt = 0;

        int Ind1 = mT.Length - 1;
        int Ind2 = CurrStr.Length - 1;
        while (0 <= Ind1 && 0 <= Ind2) {
            if (mT[Ind1] == CurrStr[Ind2]) {
                Ind1--; Ind2--;
                MatchCnt++;
            }
            else {
                Ind2--;
            }
        }
        return MatchCnt;
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        // 最後の要素がVal未満の特殊ケース
        if (pVal > pList.Last()) {
            return -1;
        }
        // 最初の要素がVal以上の特殊ケース
        if (pVal <= pList[0]) {
            return 0;
        }

        int L = 0;
        int R = pList.Count - 1;

        while (L + 1 < R) {
            int Mid = (L + R) / 2;

            if (pList[Mid] >= pVal) {
                R = Mid;
            }
            else {
                L = Mid;
            }
        }
        return R;
    }
}

解説

前処理で
先頭からの一致数と
末尾からの一致数を求めます。

それから、二分探索すれば答えを求めることができます。