AOJ 0538 IOIOI

問題へのリンク

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("1");
            WillReturn.Add("13");
            WillReturn.Add("OOIOIOIOIIOII");
            WillReturn.Add("2");
            WillReturn.Add("13");
            WillReturn.Add("OOIOIOIOIIOII");
            WillReturn.Add("0");
            //4
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        for (int I = 0; I <= InputList.Count - 1; I += 3) {
            int N = int.Parse(InputList[I]);
            if (N == 0) break;
            string SStr = InputList[I + 2];
            Solve(N, SStr);
        }
    }

    static void Solve(int pN, string pSStr)
    {
        long PLen = 3 + 2 * (pN - 1);

        var InsRollingHashUtil = new RollingHashUtil(0, 0);

        for (int I = 1; I <= PLen; I++) {
            if (I % 2 == 1) {
                InsRollingHashUtil.AddRightStr("I");
            }
            else {
                InsRollingHashUtil.AddRightStr("O");
            }
        }

        var InsRollingHash = new RollingHash(pSStr);

        long Answer = 0;

        decimal Hash1 = InsRollingHashUtil.GetRollingHash();
        long UB = pSStr.Length - 1;
        for (int I = 0; I <= UB; I++) {
            long RangeSta = I;
            long RangeEnd = I + PLen - 1;

            if (RangeEnd > UB) continue;

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

            if (Hash1 == Hash2) Answer++;
        }
        Console.WriteLine(Answer);
    }
}

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

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

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

    // コンストラクタ
    internal RollingHash(string pTargetStr)
    {
        decimal Omomi = 1;
        long UB = pTargetStr.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] += pTargetStr[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;
    }
}
#endregion

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

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

    int mStrLen;
    decimal mRollingHash;

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

        if (mOmomiArr.Length < 16) {
            mOmomiArr = new decimal[16];
            decimal Omomi = 1;
            for (int 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(int 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, int 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, int pRightLen)
    {
        decimal Omomi = GetOmomi(pRightLen);
        mRollingHash *= Omomi;
        mRollingHash %= Hou;

        mRollingHash += pRightRollingHash;
        mRollingHash %= Hou;

        mStrLen += pRightLen;
    }
}
#endregion

解説

文字列の検索なので、ローリングハッシュを使ってます。