結果
問題 | No.430 文字列検索 |
ユーザー | Michel |
提出日時 | 2020-10-28 14:12:46 |
言語 | C#(csc) (csc 3.9.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 7,051 bytes |
コンパイル時間 | 863 ms |
コンパイル使用メモリ | 112,060 KB |
実行使用メモリ | 22,912 KB |
最終ジャッジ日時 | 2024-11-10 00:48:22 |
合計ジャッジ時間 | 4,129 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 20 ms
22,912 KB |
testcase_01 | TLE | - |
testcase_02 | -- | - |
testcase_03 | -- | - |
testcase_04 | -- | - |
testcase_05 | -- | - |
testcase_06 | -- | - |
testcase_07 | -- | - |
testcase_08 | -- | - |
testcase_09 | -- | - |
testcase_10 | -- | - |
testcase_11 | -- | - |
testcase_12 | -- | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc) Copyright (C) Microsoft Corporation. All rights reserved.
ソースコード
using System; using System.Collections; using System.IO; using System.Linq; using System.Text; using System.Text.RegularExpressions; using System.Collections.Generic; using System.Threading.Tasks; /* ・概要 ハッシュ値を利用し、文字列の一致を判定する。 ハッシュ化の際に累積和的な考え方を使うことがポイント。 計算量は、O(N + M) 但し、Nは元の文字列全体の長さ、Mは検索対象文字列の長さ(文字数) --- !!! --- ・衝突の虞 但し、あくまでハッシュ値の比較なので、 ハッシュの衝突(synonymの存在)の可能性もあるので注意。 ・対策 :複数のハッシュ値(複数のパラメタ)を用意し、全てのハッシュ値が一致しているか確かめる。 (但し、ハッシュ関数の数の分、計算量が定数倍になる) →本ライブラリで言えば、コンストラクタの引数を変えて、複数のRollingHashオブジェクトを生成する。 :ハッシュ値が一致した部分が、本当に一致しているか文字列ベースで確認 (但し、これも計算量が増える) --- !!! --- ・ライブラリの使用法 1. クラスRollingHashのインスタンスを作成 この時点で、前計算にO(N)かかる。 引数は、 string 元の文字列全体S long ハッシュ化に使う定数b(デフォルトは10^5+7)、 long ハッシュ化に使う定数(素数)mod(デフォルトは10^9+7) (e.g. ) 2. Hashing関数で、元の文字列Sとは異なる文字列S2のハッシュ値を求める 一から計算するので、計算量はO(S2.Length) 引数は文字列S2(当然、元の文字列以下の長さである必要) (e.g. ) 3. GetHashBetween関数で、元の文字列Sの部分文字列(閉区間S[l,r] )のハッシュ値を取得 前計算をしているので、計算量はO(1) 引数は、該当箇所[l,r]のインデックス(閉区間なので注意) ハッシュの衝突の可能性もあるので注意(あくまで必要条件であり、十分条件とは言い切れない) (e.g. ) ・ライブラリの動作確認 AOJ ALDS1_14_B(String Search) http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_14_B&lang=jp */ class Program { //Main static void Main(string[] args) { //出力準備(AutoFlushを切る) var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false}; Console.SetOut(sw); //解答 Solve(); //出力終了 Console.Out.Flush(); } static void Solve() { /* cf. 複数のRollingHashオブジェクト(ハッシュ関数)を用意する場合の為の定数 2つ目のオブジェクトのパラメタには、例えば以下を使用してみよ */ const long secondBase = 1009; const long secondMod = 998244353; //対象となる文字列を読み込む //検索対象文字列 string S = Console.ReadLine(); //1. クラスRollingHashのインスタンスを作成 /* この時点で、前計算にO(N)かかる。 引数は、 string 元の文字列全体S long ハッシュ化に使う定数b(デフォルトは10^5+7)、 long ハッシュ化に使う定数(素数)mod(デフォルトは10^9+7) */ RollingHash rh1 = new RollingHash(S); //念の為、異なるパラメタでもう一つインスタンスを作成 RollingHash rh2 = new RollingHash(S, secondBase, secondMod); //答え(カウンター) long ans = 0; //各クエリに回答 int M = int.Parse(Console.ReadLine()); for(int q=0; q<M; q++){ //検索したい文字列 string S2 = Console.ReadLine(); //検索したい文字列の方が長い場合、次へ if(S2.Length > S.Length){ continue; } //2.Hashing関数で、元の文字列Sとは異なる文字列S2のハッシュ値を求める /* 一から計算するので、計算量はO(S2.Length) 引数は文字列S2(当然、元の文字列以下の長さである必要) */ long hash1 = rh1.Hashing(S2); //念の為、異なるハッシュ関数の方でも計算しておく long hash2 = rh2.Hashing(S2); //3. GetHashBetween関数で、元の文字列Sの部分文字列(閉区間S[l,r] )のハッシュ値を取得 /* 前計算をしているので、計算量はO(1) 引数は、該当箇所[l,r]のインデックス(閉区間なので注意) ハッシュの衝突の可能性もあるので注意(あくまで必要条件であり、十分条件とは言い切れない) */ //Sの部分文字列で、S2と一致する部分を検索 /* 検索範囲に注意(0 <= i < S.Length - S2.Length + 1) */ for(int i=0; i<S.Length - S2.Length + 1; i++){ //A. S[l,r]のハッシュ値を取得 long h1 = rh1.GetHashBetween(i, i+S2.Length-1); //念の為、異なるハッシュ関数の方でも計算しておく long h2 = rh2.GetHashBetween(i, i+S2.Length-1); //B. 検索対象とハッシュ値が一致しているかチェック if(h1 == hash1){ //もう片方のハッシュ値も一致しているか、念の為チェック if(h2 == hash2){ //2種類のハッシュ値が一致しているので、恐らく元の文字列は等しい ans ++; } } } } Console.WriteLine(ans); } } class RollingHash { public long B,MOD; public string S; public int N; public long[] Power; public long[] Hash; //コンストラクタ /* この時点で、前計算としてO(N) 引数は、 string 元の文字列全体S long ハッシュ化に使う定数b(デフォルトは10^5+7)、 long ハッシュ化に使う定数(素数)mod(デフォルトは10^9+7) */ public RollingHash(string s, long b = 100007, long mod = 1000000007) { this.S = s; this.B = b; this.MOD = mod; this.N = s.Length; //B^nを前計算 this.Power = new long[this.N + 1]; this.Power[0] = 1; for (int i=0; i<N; i++) { this.Power[i+1] = (this.Power[i] * B) % MOD; } //ハッシュを前計算 this.Hash = new long[this.N + 1]; for (int i=0; i<N; i++) { this.Hash[i+1] = (this.Hash[i] * B + S[i]) % MOD; } } //閉区間S[l,r] のハッシュ値を求める /* 引数は、該当箇所[l,r]のインデックス(閉区間なので注意) */ public long GetHashBetween(int l, int r) { r ++; long hash = this.Hash[r] - (this.Hash[l] * this.Power[r - l] % MOD); if (hash < 0) hash += MOD; return hash; } //引数として与えた文字列S2のハッシュ値を求める /* 元の文字列Sとは異なる文字列S2をハッシュ化したいときに使う 引数は文字列S2(当然、元の文字列以下の長さである必要) 計算量は、O(S2.Length) */ public long Hashing(string s2) { long hash = 0; for(int i=0; i<s2.Length; i++){ hash += (s2[i] * this.Power[s2.Length-i-1] % this.MOD); hash %= this.MOD; } return hash; } }