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