結果

問題 No.430 文字列検索
コンテスト
ユーザー bluemegane
提出日時 2021-05-15 12:44:40
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 1,756 bytes
コンパイル時間 2,198 ms
コンパイル使用メモリ 113,300 KB
実行使用メモリ 19,840 KB
最終ジャッジ日時 2024-11-10 00:55:47
合計ジャッジ時間 23,287 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 4 TLE * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;

class RollingHash
{
    public const ulong B = (ulong)1e9 + 7;
    public string S { get; set; }
    public int N { get; set; }
    public ulong[] Power { get; set; }
    public ulong[] Hash { get; set; }
    public RollingHash(string s)
    {
        this.S = s;
        this.N = s.Length;
        this.Power = new ulong[this.N + 1];
        this.Power[0] = 1;
        for (int i = 0; i < N; i++) this.Power[i + 1] = this.Power[i] * B;
        this.Hash = new ulong[this.N + 1];
        for (int i = 0; i < N; i++) this.Hash[i + 1] = this.Hash[i] * B + S[i];
    }
    public ulong Get(int l, int r) => this.Hash[r] - (this.Hash[l] * this.Power[r - l]);
}

public class P
{
    public string c { get; set; }
    public ulong rh { get; set; }
    public int cL { get; set; }
}

public class Hello
{
    static void Main()
    {
        var s = Console.ReadLine().Trim();
        var m = int.Parse(Console.ReadLine().Trim());
        var ps = new P[m];
        for (int i = 0; i < m; i++)
        {
            var t = Console.ReadLine().Trim();
            var tL = t.Length;
            var rh = new RollingHash(t);
            var t2 = rh.Get(0, tL);
            ps[i] = new P { c = t, cL = tL, rh = t2 };
        }
        getAns(s, m, ps);
    }
    static void getAns(string s, int m, P[] ps)
    {
        var rh = new RollingHash(s);
        var sL = s.Length;
        var p = 0;
        var count = 0;
        while (p < sL)
        {
            foreach (var x in ps)
            {
                if (p + x.cL <= sL)
                {
                    var a0 = rh.Get(p, p + x.cL);
                    if (a0 == x.rh) count++;
                }
            }
            p++;
        }
        Console.WriteLine(count);
    }
}
0