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