ABC452-D No-Subsequence Substring

問題へのリンク

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("abrakadabra");
            WillReturn.Add("aba");
            //51
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("aaaaa");
            WillReturn.Add("a");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("rdddrdtdcdrrdcredctdordoeecrotet");
            WillReturn.Add("dcre");
            //263
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        char[] SArr = InputList[0].ToCharArray();
        long UB_SArr = SArr.GetUpperBound(0);

        char[] TArr = InputList[1].ToCharArray();
        long UB_TArr = TArr.GetUpperBound(0);

        // IndのList[文字]なDict
        var IndListDict = new Dictionary<char, List<long>>();

        for (char I = 'a'; I <= 'z'; I++) {
            IndListDict[I] = new List<long>();
        }

        for (long I = 0; I <= UB_SArr; I++) {
            IndListDict[SArr[I]].Add(I);
        }

        long Answer = 0;
        for (long I = 0; I <= UB_SArr; I++) {
            long CurrInd = I;

            // 右端の制限の有無
            bool IsInf = false;

            for (long J = 0; J <= UB_TArr; J++) {
                char EachChar = TArr[J];
                long ResultInd = ExecNibunhou_LowerBound(CurrInd, IndListDict[EachChar]);
                if (ResultInd == -1) {
                    IsInf = true;
                    break;
                }
                CurrInd = IndListDict[EachChar][(int)ResultInd];
                if (J < UB_TArr) {
                    // 最終値でなければ、添字をインクリメント
                    CurrInd++;
                }
            }
            long CurrAnswer = 0;
            if (IsInf) {
                // 右端の制限が無い場合
                CurrAnswer = UB_SArr - I + 1;
            }
            else {
                // 右端の制限がある場合
                CurrAnswer = CurrInd - I;
            }
            Answer += CurrAnswer;
        }
        Console.WriteLine(Answer);
    }

    // 二分法で、Val以上で最小の値を持つ、添字を返す
    static int ExecNibunhou_LowerBound(long pVal, List<long> pList)
    {
        if (pList.Count == 0) return -1;

        // 最後の要素が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;
    }
}

解説

OKな区間の左端を全探索し、
右端は、Tの長さ分、LowerBoundを繰り返してます。