結果
| 問題 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| 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.
ソースコード
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;
}
}