結果

問題 No.430 文字列検索
ユーザー MichelMichel
提出日時 2020-10-28 14:12:46
言語 C#(csc)
(csc 3.9.0)
結果
TLE  
実行時間 -
コード長 7,051 bytes
コンパイル時間 940 ms
コンパイル使用メモリ 61,440 KB
実行使用メモリ 24,044 KB
最終ジャッジ日時 2023-09-29 03:37:53
合計ジャッジ時間 5,040 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 57 ms
22,816 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 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

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;
	}
}
0