A56 String Hash

問題へのリンク

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("7 3");
            WillReturn.Add("abcbabc");
            WillReturn.Add("1 3 5 7");
            WillReturn.Add("1 5 2 6");
            WillReturn.Add("1 2 6 7");
            //Yes
            //No
            //No
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        string S = InputList[1];

        var InsRollingHash = new RollingHash(S);

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(2)) {
            SplitAct(EachStr);
            int A = wkArr[0] - 1;
            int B = wkArr[1] - 1;
            int C = wkArr[2] - 1;
            int D = wkArr[3] - 1;

            long Hash1 = InsRollingHash.GetRangeHash(A, B);
            long Hash2 = InsRollingHash.GetRangeHash(C, D);
            if (Hash1 == Hash2) {
                sb.AppendLine("Yes");
            }
            else {
                sb.AppendLine("No");
            }
        }
        Console.Write(sb.ToString());
    }
}

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

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

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

    // コンストラクタ
    internal RollingHash(string pTargetStr)
    {
        long Omomi = 1;
        long UB = pTargetStr.Length - 1;

        mHashArr = new long[UB + 1];
        mOmomiArr = new long[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] += pTargetStr[I];
            mHashArr[I] %= Hou;
            Omomi *= Base;
            Omomi %= Hou;
        }
    }

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

解説

ローリングハッシュを使ってます。