結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 Michel
|
| 提出日時 | 2020-10-28 14:33:50 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
AC
|
| 実行時間 | 653 ms / 2,000 ms |
| コード長 | 7,167 bytes |
| コンパイル時間 | 887 ms |
| コンパイル使用メモリ | 111,032 KB |
| 実行使用メモリ | 22,272 KB |
| 最終ジャッジ日時 | 2024-11-10 00:48:31 |
| 合計ジャッジ時間 | 7,944 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 22 ms
17,920 KB |
| testcase_01 | AC | 629 ms
22,144 KB |
| testcase_02 | AC | 653 ms
22,016 KB |
| testcase_03 | AC | 644 ms
22,016 KB |
| testcase_04 | AC | 22 ms
17,664 KB |
| testcase_05 | AC | 22 ms
17,664 KB |
| testcase_06 | AC | 21 ms
17,536 KB |
| testcase_07 | AC | 21 ms
17,536 KB |
| testcase_08 | AC | 41 ms
21,888 KB |
| testcase_09 | AC | 21 ms
17,536 KB |
| testcase_10 | AC | 26 ms
17,536 KB |
| testcase_11 | AC | 637 ms
22,272 KB |
| testcase_12 | AC | 634 ms
22,144 KB |
| testcase_13 | AC | 635 ms
21,888 KB |
| testcase_14 | AC | 636 ms
22,144 KB |
| testcase_15 | AC | 638 ms
22,144 KB |
| testcase_16 | AC | 628 ms
22,144 KB |
| testcase_17 | AC | 623 ms
21,888 KB |
コンパイルメッセージ
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オブジェクトを生成する。
：ハッシュ値が一致した部分が、本当に一致しているか文字列ベースで確認
（但し、これも計算量が増える）
--- !!! ---
--- !!! ---
・ハッシュ値の計算量
累積和を使用するのでO(1)ではあるが、MODの計算等でもたつく。
同じ範囲のハッシュ値を何度も使う場合は、計算結果を保存しておいて再利用すべし。
（e.g. yukicoder No.430 文字列検索
（https://yukicoder.me/problems/no/430））
--- !!! ---
・ライブラリの使用法
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);
//1 <= Ci <= 10なので、hash値を予め求めておく
long[][] hashTable = new long[10][];
for(int i=1; i<=10; i++){
//Sの長さを超える場合、終了
if(S.Length < i){
break;
}
hashTable[i-1] = new long[S.Length - i + 1];
for(int j=0; j<S.Length - i + 1; j++){
//S[l,r]のハッシュ値を取得
long h1 = rh1.GetHashBetween(j, i+j-1);
hashTable[i-1][j] = h1;
}
}
//答え（カウンター）
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);
//3. GetHashBetween関数で、元の文字列Sの部分文字列（閉区間S[l,r] ）のハッシュ値を取得
/*
前計算をしているので、計算量はO(1)
引数は、該当箇所[l,r]のインデックス（閉区間なので注意）
ハッシュの衝突の可能性もあるので注意（あくまで必要条件であり、十分条件とは言い切れない）
*/
//Sの部分文字列で、S2と一致する部分を検索
/*
検索範囲に注意（0 <= i < S.Length - S2.Length + 1）
*/
foreach(long h1 in hashTable[S2.Length-1]){
if(hash1 == h1){
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] のハッシュ値を求める
/*
計算量はO(1)だが、計算内容が多いので、同じ値を繰り返し使うなら保存しておくべき。
引数は、該当箇所[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;
}
}