結果

問題 No.430 文字列検索
コンテスト
ユーザー 👑 terry_u16
提出日時 2020-08-10 16:33:16
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 4,321 bytes
コンパイル時間 2,143 ms
コンパイル使用メモリ 113,964 KB
実行使用メモリ 25,984 KB
最終ジャッジ日時 2024-11-10 00:45:20
合計ジャッジ時間 4,192 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other AC * 1 TLE * 1 -- * 12
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;

namespace ConsoleApp5
{
    class Program
    {
        static void Main(string[] args)
        {
            var s = new RollingHash(Console.ReadLine());
            var m = int.Parse(Console.ReadLine());
            long count = 0;
            for (int i = 0; i < m; i++)
            {
                var c = new RollingHash(Console.ReadLine());
                var cHash = c[..];
                for (int begin = 0; begin <= s.Length - c.Length; begin++)
                {
                    if (cHash == s.Slice(begin, c.Length))
                    {
                        count++;
                    }
                }
            }

            Console.WriteLine(count);
        }

        /// <summary>
        /// 参考: https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
        /// ジェネリクスに対応させるにはGetHashCode()を足していく？実装によっては重そうなのでとりあえずパス。
        /// </summary>
        class RollingHash
        {
            const ulong Mask30 = (1UL << 30) - 1;
            const ulong Mask31 = (1UL << 31) - 1;
            const ulong Mod = (1UL << 61) - 1;
            const ulong Positivizer = Mod * ((1UL << 3) - 1);   // 引き算する前に足すことでmodが負になることを防ぐやつ
            static readonly uint base1;
            static readonly uint base2;
            static readonly List<ulong> pow1;
            static readonly List<ulong> pow2;

            static RollingHash()
            {
                var random = new Random();
                base1 = (uint)random.Next(129, int.MaxValue >> 2);
                base2 = (uint)random.Next(int.MaxValue >> 2, int.MaxValue); // 32bit目は0にしておく
                pow1 = new List<ulong>() { 1 };
                pow2 = new List<ulong>() { 1 };
            }

            ulong[] hash1;
            ulong[] hash2;
            public int Length => hash1.Length - 1;

            public RollingHash(ReadOnlySpan<char> s)
            {
                hash1 = new ulong[s.Length + 1];
                hash2 = new ulong[s.Length + 1];

                for (int i = pow1.Count; i < s.Length + 1; i++)
                {
                    pow1.Add(CalculateModular(Multiply(pow1[i - 1], base1)));
                    pow2.Add(CalculateModular(Multiply(pow2[i - 1], base2)));
                }

                for (int i = 0; i < s.Length; i++)
                {
                    hash1[i + 1] = CalculateModular(Multiply(hash1[i], base1) + s[i]);
                    hash2[i + 1] = CalculateModular(Multiply(hash2[i], base2) + s[i]);
                }
            }

            public (ulong, ulong) this[Range range]
            {
                get
                {
                    var (offset, length) = range.GetOffsetAndLength(Length);
                    return Slice(offset, length);
                }
            }

            public (ulong, ulong) Slice(int begin, int length)
            {
                var result1 = CalculateModular(hash1[begin + length] + Positivizer - Multiply(hash1[begin], pow1[length]));
                var result2 = CalculateModular(hash2[begin + length] + Positivizer - Multiply(hash2[begin], pow2[length]));
                return (result1, result2);
            }

            private static ulong Multiply(ulong l, ulong r)
            {
                var lu = l >> 31;
                var ll = l & Mask31;
                var ru = r >> 31;
                var rl = r & Mask31;
                var mid = ll * ru + lu * rl;
                return ((lu * ru) << 1) + ll * rl + ((mid & Mask30) << 31) + (mid >> 30);   // a * 2^61 ≡ a (mod 2^61 - 1)を使う
            }

            private static ulong Multiply(ulong l, uint r)
            {
                var lu = l >> 31;
                var mid = lu * r;
                return (l & Mask31) * r + ((mid & Mask30) << 31) + (mid >> 30); // rの32bit目は0としている
            }

            private static ulong CalculateModular(ulong value)
            {
                value = (value & Mod) + (value >> 61);
                if (value >= Mod)
                {
                    value -= Mod;
                }
                return value;
            }
        }


    }
}
0