ABC284-F ABCBAC

問題へのリンク

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("abcbac");
            //abc
            //2
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("4");
            WillReturn.Add("abababab");
            //abab
            //1
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("3");
            WillReturn.Add("agccga");
            //cga
            //0
        }
        else if (InputPattern == "Input4") {
            WillReturn.Add("4");
            WillReturn.Add("atcodeer");
            //-1
        }
        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();
        long N = long.Parse(InputList[0]);

        string TSei = InputList[1];
        string TRev = new string(TSei.ToCharArray().Reverse().ToArray());
        long UB = TSei.Length - 1;

        var InsRollingHashSei = new RollingHash(TSei);
        var InsRollingHashRev = new RollingHash(TRev);

        decimal GoalHash = InsRollingHashSei.GetRangeHash(0, UB);

        // 正文字列の区間を引数とし、指定区間の文字列を反転したハッシュ値を返す
        Func<long, long, decimal> GetRevHash = (pSta, pEnd) =>
        {
            long NewSta = UB - pEnd;
            long NewEnd = UB - pSta;
            return InsRollingHashRev.GetRangeHash(NewSta, NewEnd);
        };

        // Iを全探索
        for (long I = 0; I <= N; I++) {
            if (I == 0) {
                // 先頭付与が0文字の場合
                long RangeSta = 0;
                long RangeEnd = RangeSta + N - 1;

                decimal Hash2 = InsRollingHashSei.GetRangeHash(RangeSta, RangeEnd);
                decimal Hash3 = GetRevHash(RangeSta, RangeEnd);
                var InsRollingHashUtil = new RollingHashUtil(Hash2, N);
                InsRollingHashUtil.AddRightHash(Hash3, N);
                if (InsRollingHashUtil.GetRollingHash() == GoalHash) {
                    Console.WriteLine(GetRevStr(TSei.Substring((int)RangeSta, (int)N)));
                    Console.WriteLine(I);
                    return;
                }
            }
            else if (I == N) {
                // 先頭付与がN文字の場合
                long RangeSta = N;
                long RangeEnd = RangeSta + N - 1;

                decimal Hash2 = InsRollingHashSei.GetRangeHash(RangeSta, RangeEnd);
                decimal Hash1 = GetRevHash(RangeSta, RangeEnd);
                var InsRollingHashUtil = new RollingHashUtil(Hash2, N);
                InsRollingHashUtil.AddLeftHash(Hash1, N);
                if (InsRollingHashUtil.GetRollingHash() == GoalHash) {
                    Console.WriteLine(GetRevStr(TSei.Substring((int)RangeSta, (int)N)));
                    Console.WriteLine(I);
                    return;
                }
            }
            else {
                // 先頭付与がI文字の場合
                long RangeSta = I;
                long RangeEnd = RangeSta + N - 1;

                decimal Hash2 = InsRollingHashSei.GetRangeHash(RangeSta, RangeEnd);

                decimal Hash1 = GetRevHash(RangeEnd - I + 1, RangeEnd);

                long Rest = N - I;
                decimal Hash3 = GetRevHash(RangeSta, RangeSta + Rest - 1);

                var InsRollingHashUtil = new RollingHashUtil(Hash2, N);
                InsRollingHashUtil.AddLeftHash(Hash1, I);
                InsRollingHashUtil.AddRightHash(Hash3, Rest);
                if (InsRollingHashUtil.GetRollingHash() == GoalHash) {
                    Console.WriteLine(GetRevStr(TSei.Substring((int)RangeSta, (int)N)));
                    Console.WriteLine(I);
                    return;
                }
            }
        }
        Console.WriteLine(-1);
    }

    ////////////////////////////////////////////////////////////////
    // string型を引数とし、reverse
    ////////////////////////////////////////////////////////////////
    static string GetRevStr(string pStr)
    {
        char[] wkArr = pStr.ToCharArray();
        Array.Reverse(wkArr);
        return new string(wkArr);
    }
}

#region RollingHash
// ローリングハッシュ
internal class RollingHash
{
    const decimal Base = 100M;
    const decimal Hou = 67280421310721M;

    // ハッシュ値[終了Ind]で、[0,終了Ind]のハッシュ値を保持
    internal decimal[] mHashArr;

    // 桁の重みの配列
    decimal[] mOmomiArr;

    string mBaseStr;

    long UB; // コンストラクタで渡した文字列のUB

    // コンストラクタ
    internal RollingHash(string pBaseStr)
    {
        mBaseStr = pBaseStr;

        decimal Omomi = 1;
        UB = pBaseStr.Length - 1;

        mHashArr = new decimal[UB + 1];
        mOmomiArr = new decimal[UB + 1];
        for (int I = 0; I <= UB; I++) {
            mOmomiArr[I] = Omomi;
            if (I > 0) {
                mHashArr[I] += mHashArr[I - 1] * Base;
                mHashArr[I] %= Hou;
            }
            mHashArr[I] += pBaseStr[I];
            mHashArr[I] %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }
    }

    // [Sta,End]のハッシュ値を返す
    internal decimal GetRangeHash(long pSta, long pEnd)
    {
        decimal WillReturn = mHashArr[pEnd];
        if (pSta > 0) {
            long Range = pEnd - pSta + 1;
            decimal PrevVal = mHashArr[pSta - 1];
            decimal MinusVal = PrevVal * mOmomiArr[Range];
            MinusVal %= Hou;
            WillReturn -= MinusVal;
            if (WillReturn < 0) {
                WillReturn += Hou;
            }
        }
        return WillReturn;
    }

    // 左の文字数、追加文字列を引数とし、
    // 間に文字列をInsertした時のハッシュ値を返す
    internal decimal GetInsertedHash(long pLeftCnt, string pInsertStr)
    {
        if (pLeftCnt > mBaseStr.Length) {
            throw new Exception("pLeftCntにmBaseStr.lengthより大きい値が指定されました。");
        }

        long RightCnt = mBaseStr.Length - pLeftCnt;

        // 重み配列が不足してたら、補完する
        if (mOmomiArr.GetUpperBound(0) < RightCnt) {
            decimal[] NewOmomiArr = new decimal[mOmomiArr.Length * 2];
            mOmomiArr.CopyTo(NewOmomiArr, 0);

            for (long I = mOmomiArr.GetUpperBound(0) + 1; I <= NewOmomiArr.GetUpperBound(0); I++) {
                decimal NewVal = NewOmomiArr[I - 1];
                NewVal *= Base;
                NewVal %= Hou;
                NewOmomiArr[I] = NewVal;
            }
            mOmomiArr = NewOmomiArr;
        }

        // 右のハッシュ値
        decimal HashRight = 0;
        if (RightCnt > 0) {
            HashRight = GetRangeHash(UB - RightCnt + 1, UB);
        }

        // 中央のハッシュ値
        decimal Omomi = mOmomiArr[RightCnt];
        decimal HashMid = 0;
        foreach (char EachChar in pInsertStr) {
            HashMid += Omomi * EachChar;
            HashMid %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }

        // 左のハッシュ値
        decimal HashLeft = 0;
        if (pLeftCnt > 0) {
            HashLeft = GetRangeHash(0, pLeftCnt - 1);

            // 重みを掛ける
            HashLeft *= Omomi;
            HashLeft %= Hou;
        }

        decimal Result = HashLeft;
        Result += HashMid;
        Result %= Hou;
        Result += HashRight;
        Result %= Hou;
        return Result;
    }
}
#endregion

#region RollingHashUtil
// ローリングハッシュのutilクラス
internal class RollingHashUtil
{
    const decimal Base = 100M;
    const decimal Hou = 67280421310721M;

    // 桁の重みの配列
    static decimal[] mOmomiArr = new decimal[0];

    long mStrLen;
    decimal mRollingHash;

    // コンストラクタ
    // Hash値と、長さを指定
    internal RollingHashUtil(decimal pRollingHash, long pStrLen)
    {
        mStrLen = pStrLen;
        mRollingHash = pRollingHash;

        if (mOmomiArr.Length < 16) {
            mOmomiArr = new decimal[16];
            decimal Omomi = 1;
            for (long I = 0; I <= mOmomiArr.GetUpperBound(0); I++) {
                mOmomiArr[I] = Omomi;
                Omomi *= Base;
                Omomi %= Hou;
            }
        }
    }

    // 桁の重みを返す
    // 引数が0なら、1をreturn
    // 引数が1なら、100をreturn
    // 引数が2なら、10000をreturn
    static private decimal GetOmomi(long pInd)
    {
        // 重み配列が不足してたら、補完する
        while (mOmomiArr.GetUpperBound(0) < pInd) {
            decimal[] NewOmomiArr = new decimal[mOmomiArr.Length * 2];
            mOmomiArr.CopyTo(NewOmomiArr, 0);

            for (long I = mOmomiArr.GetUpperBound(0) + 1; I <= NewOmomiArr.GetUpperBound(0); I++) {
                decimal NewVal = NewOmomiArr[I - 1];
                NewVal *= Base;
                NewVal %= Hou;
                NewOmomiArr[I] = NewVal;
            }
            mOmomiArr = NewOmomiArr;
        }
        return mOmomiArr[pInd];
    }

    // ハッシュ値を返す
    internal decimal GetRollingHash()
    {
        return mRollingHash;
    }

    // 文字列長を返す
    internal decimal GetStrLen()
    {
        return mStrLen;
    }

    // 文字列のハッシュ値を求める
    static decimal DeriveRollingHash(string pTargetStr)
    {
        decimal WillReturn = 0;
        decimal Omomi = 1;
        foreach (char EachChar in pTargetStr) {
            WillReturn += Omomi * EachChar;
            WillReturn %= Hou;

            Omomi *= Base;
            Omomi %= Hou;
        }
        return WillReturn;
    }

    // 左に文字列を追加(string指定)
    internal void AddLeftStr(string pLeftStr)
    {
        decimal LeftRollingHash = DeriveRollingHash(pLeftStr);
        decimal Omomi = GetOmomi(mStrLen);
        LeftRollingHash *= Omomi;
        LeftRollingHash %= Hou;

        mRollingHash += LeftRollingHash;
        mRollingHash %= Hou;

        mStrLen += pLeftStr.Length;
    }

    // 左に文字列を追加(Hash値と、長さを指定)
    internal void AddLeftHash(decimal pLeftRollingHash, long pLeftLen)
    {
        decimal Omomi = GetOmomi(mStrLen);
        pLeftRollingHash *= Omomi;
        pLeftRollingHash %= Hou;

        mRollingHash += pLeftRollingHash;
        mRollingHash %= Hou;

        mStrLen += pLeftLen;
    }

    // 右に文字列を追加(string指定)
    internal void AddRightStr(string pRightStr)
    {
        decimal RightRollingHash = DeriveRollingHash(pRightStr);
        decimal Omomi = GetOmomi(pRightStr.Length);
        mRollingHash *= Omomi;
        mRollingHash %= Hou;

        mRollingHash += RightRollingHash;
        mRollingHash %= Hou;

        mStrLen += pRightStr.Length;
    }

    // 右に文字列を追加(Hash値と、長さを指定)
    internal void AddRightHash(decimal pRightRollingHash, long pRightLen)
    {
        decimal Omomi = GetOmomi(pRightLen);
        mRollingHash *= Omomi;
        mRollingHash %= Hou;

        mRollingHash += pRightRollingHash;
        mRollingHash %= Hou;

        mStrLen += pRightLen;
    }
}
#endregion

解説

Iが決まれば、反転したN文字を配置する箇所が決定するので
Iを全探索してます。

前処理で、
反転した文字列での、区間ハッシュ値を高速に求めれるようにしてます。