結果

問題 No.430 文字列検索
ユーザー terry_u16terry_u16
提出日時 2020-08-10 16:38:42
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 151 ms / 2,000 ms
コード長 4,882 bytes
コンパイル時間 945 ms
コンパイル使用メモリ 107,520 KB
実行使用メモリ 52,212 KB
最終ジャッジ日時 2024-11-10 00:45:19
合計ジャッジ時間 3,014 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 25 ms
18,816 KB
testcase_01 AC 151 ms
52,212 KB
testcase_02 AC 110 ms
22,656 KB
testcase_03 AC 110 ms
22,656 KB
testcase_04 AC 27 ms
18,688 KB
testcase_05 AC 26 ms
18,816 KB
testcase_06 AC 28 ms
18,816 KB
testcase_07 AC 27 ms
18,688 KB
testcase_08 AC 149 ms
51,312 KB
testcase_09 AC 27 ms
18,816 KB
testcase_10 AC 37 ms
22,144 KB
testcase_11 AC 121 ms
27,136 KB
testcase_12 AC 123 ms
27,392 KB
testcase_13 AC 123 ms
27,392 KB
testcase_14 AC 122 ms
25,088 KB
testcase_15 AC 119 ms
24,576 KB
testcase_16 AC 112 ms
22,912 KB
testcase_17 AC 112 ms
22,912 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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 counts = new Dictionary<(ulong, ulong), long>();

            for (int begin = 0; begin < s.Length; begin++)
            {
                for (int length = 1; length <= 10; length++)
                {
                    if (begin + length > s.Length)
                    {
                        break;
                    }

                    var hash = s.Slice(begin, length);
                    if (counts.ContainsKey(hash))
                    {
                        counts[hash]++;
                    }
                    else
                    {
                        counts[hash] = 1;
                    }
                }
            }

            var m = int.Parse(Console.ReadLine());
            long result = 0;
            for (int i = 0; i < m; i++)
            {
                var c = new RollingHash(Console.ReadLine());
                var cHash = c[..];
                if (counts.ContainsKey(cHash))
                {
                    result += counts[cHash];
                }
            }

            Console.WriteLine(result);
        }

        /// <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