結果
| 問題 | No.430 文字列検索 |
| ユーザー |
 Michel
|
| 提出日時 | 2020-10-28 14:31:38 |
| 言語 | C#(csc) (csc 3.9.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 7,087 bytes |
| コンパイル時間 | 817 ms |
| コンパイル使用メモリ | 106,624 KB |
| 実行使用メモリ | 22,016 KB |
| 最終ジャッジ日時 | 2024-11-10 00:48:26 |
| 合計ジャッジ時間 | 7,591 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 20 ms
17,536 KB |
| testcase_01 | AC | 604 ms
22,016 KB |
| testcase_02 | AC | 608 ms
21,888 KB |
| testcase_03 | AC | 599 ms
21,888 KB |
| testcase_04 | RE | - |
| testcase_05 | AC | 19 ms
17,792 KB |
| testcase_06 | RE | - |
| testcase_07 | AC | 20 ms
17,792 KB |
| testcase_08 | AC | 38 ms
21,632 KB |
| testcase_09 | RE | - |
| testcase_10 | AC | 22 ms
17,548 KB |
| testcase_11 | AC | 591 ms
21,888 KB |
| testcase_12 | AC | 594 ms
22,016 KB |
| testcase_13 | AC | 617 ms
22,016 KB |
| testcase_14 | AC | 589 ms
21,888 KB |
| testcase_15 | AC | 583 ms
21,888 KB |
| testcase_16 | AC | 599 ms
22,016 KB |
| testcase_17 | AC | 602 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++){
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;
}
}