07/25 文字列探索の続き。

課題 １ 剰余演算の性質

bc は任意に大きな整数の演算ができるソフトウェアである。以下の計算結果を 求めよ。

bc を終了するには quit と入力すれば良い。

課題 ２ Rabin-Karp 法

以下は Rabin-Karp 法による文字列探索プログラムである。完成させて、 動作をテストしなさい。 

int RabinKarp( string & pattern, string & text )
{
    const int q = 815333;   // 適当な大きさの素数
    const int d = 128;      // ASCII コードの上限

    if ( text.size() < pattern.size() ) return text.size();

    int n = pattern.size();

    int pattern_hash = 0;               // パターンのハッシュ値
    for( int i = 0; i < n; i ++ )
        pattern_hash = ( pattern_hash * d + pattern[i] ) % q;

    int high_factor = 1;               // d^(n-1) % q 
    for( int i = 0; i < n-1; i ++ )
        high_factor = ( high_factor * d ) % q;

    int text_hash = 0;
    int t;
    for( t = 0; t < n; t ++ ) {
        text_hash = ( text_hash * d + text[t] ) % q;
    }
    
    if ( text_hash == pattern_hash ) { 
        if ( text.substr( 0, n ) == pattern ) 
             return 0;                         // 先頭で一致
    }

    while( t < text.size() ) 
    {
        /*    空白(b) 
              テキスト中での位置を１文字ずらした時の text_hash を計算する。 

              注意： 負の数の剰余（%）は正しく計算されない。
              % q をする前の値が負になる可能性がある場合は、
              事前に qの適当な整数倍を足しておくこと。
        */
        t++;

        if ( text_hash == pattern_hash ) {
            if ( text.substr( t-n, n ) == pattern ) 
                 return /*   空白(a)   */;
        }
    }
    return text.size();
}