#572044 (C#(csc)) No.430 文字列検索

提出ソース

結果

問題	No.430 文字列検索
ユーザー	Michel
提出日時	2020-10-28 14:33:50
言語	C#(csc) (csc 3.9.0)
結果	AC
実行時間	650 ms / 2,000 ms
コード長	7,167 bytes
コンパイル時間	843 ms
コンパイル使用メモリ	68,004 KB
実行使用メモリ	27,200 KB
最終ジャッジ日時	2023-09-29 03:39:05
合計ジャッジ時間	8,696 ms
ジャッジサーバーID （参考情報）	judge15 / judge11

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	56 ms 22,764 KB
testcase_01	AC	650 ms 25,068 KB
testcase_02	AC	637 ms 25,112 KB
testcase_03	AC	642 ms 25,028 KB
testcase_04	AC	57 ms 22,688 KB
testcase_05	AC	56 ms 20,756 KB
testcase_06	AC	56 ms 22,800 KB
testcase_07	AC	57 ms 20,768 KB
testcase_08	AC	79 ms 25,100 KB
testcase_09	AC	57 ms 20,756 KB
testcase_10	AC	61 ms 20,768 KB
testcase_11	AC	642 ms 25,092 KB
testcase_12	AC	644 ms 25,072 KB
testcase_13	AC	644 ms 25,084 KB
testcase_14	AC	646 ms 27,092 KB
testcase_15	AC	646 ms 25,096 KB
testcase_16	AC	641 ms 27,200 KB
testcase_17	AC	644 ms 23,024 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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