ABC346-F SSttrriinngg in StringString

問題へのリンク

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");
            WillReturn.Add("abc");
            WillReturn.Add("ab");
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            WillReturn.Add("abc");
            WillReturn.Add("arc");
            //0
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("1000000000000");
            WillReturn.Add("kzazkakxkk");
            WillReturn.Add("azakxk");
            //344827586207
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static Dictionary<char, List<long>> mIndListDict = new Dictionary<char, List<long>>();

    static void Main()
    {
        List<string> InputList = GetInputList();
        long N = long.Parse(InputList[0]);
        string S = InputList[1];
        string T = InputList[2];

        char[] SArr = S.ToCharArray();

        mIndListDict.Clear();
        for (long I = 0; I <= SArr.GetUpperBound(0); I++) {
            char CurrChar = SArr[I];
            if (mIndListDict.ContainsKey(CurrChar) == false) {
                mIndListDict[CurrChar] = new List<long>();
            }
            mIndListDict[CurrChar].Add(I);
        }

        // 1が達成不能な場合
        if (IsSubstr(T, 1, S, N) == false) {
            Console.WriteLine(0);
            return;
        }

        long L = 1;
        long R = long.MaxValue;

        while (L + 1 < R) {
            long Mid = R / 2;
            if (R < long.MaxValue) {
                Mid = (L + R) / 2;
            }

            if (IsSubstr(T, Mid, S, N)) {
                L = Mid;
            }
            else {
                R = Mid;
            }
        }
        Console.WriteLine(L);
    }

    // Tの各文字をK回繰り返した文字列が、SをN回繰り返した文字列の部分列かを判定
    static bool IsSubstr(string pT, long pK, string pS, long pN)
    {
        long CurrInd = -1;   // 現在のInd
        long CurrSyuume = 1; // 何週目か

        long Hou = pS.Length;

        foreach (char EachT in pT) {
            if (mIndListDict.ContainsKey(EachT) == false) {
                return false;
            }

            List<long> IndList = mIndListDict[EachT];
            long ResultInd = ExecNibunhou_UpperBound(CurrInd, IndList);
            if (ResultInd == -1) {
                if (++CurrSyuume > pN) return false;
                CurrInd = IndList[0];
                ResultInd = 0;
            }
            else {
                CurrInd = IndList[(int)ResultInd];
            }

            long RestMatchCnt = pK - 1;
            if (RestMatchCnt == 0) continue;

            // 1周以上できる場合
            if (RestMatchCnt >= IndList.Count) {
                long Div = RestMatchCnt / IndList.Count;
                CurrSyuume += Div;
                RestMatchCnt %= IndList.Count;
            }
            if (CurrSyuume > pN) return false;
            if (RestMatchCnt == 0) continue;

            // UBまで移動
            long MoveCnt = (IndList.Count - 1) - ResultInd;
            MoveCnt = Math.Min(MoveCnt, RestMatchCnt);
            CurrInd = IndList[(int)(ResultInd + MoveCnt)];
            RestMatchCnt -= MoveCnt;

            if (RestMatchCnt == 0) continue;

            // 0に移動
            CurrInd = IndList[0];
            if (++CurrSyuume > pN) return false;
            RestMatchCnt--;
            if (RestMatchCnt == 0) continue;

            // 0から移動
            MoveCnt = IndList.Count - 1;
            MoveCnt = Math.Min(MoveCnt, RestMatchCnt);
            CurrInd = IndList[(int)(MoveCnt)];
        }

        return true;
    }

    // 二分法で、Val超えで最小の値を持つ、添字を返す
    static long ExecNibunhou_UpperBound(long pVal, List<long> pList)
    {
        // 要素が0件のケース
        if (pList.Count == 0) return -1;

        // 最後の要素がVal以下の特殊ケース
        if (pVal >= pList.Last()) {
            return -1;
        }
        // 最初の要素がVal超えの特殊ケース
        if (pVal < pList[0]) {
            return 0;
        }

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

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

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

解説

答えを二分探索してます。