文字列照合

課題１

以下の力まかせ法による文字列探索プログラムを完成させなさい。 幾つかのテキスト、パターンを与えて、結果が正しいことを確認しなさい。 

int bruteforce( string & pattern, string & text )
{
    int t = 0;
    int p = 0;

    while( t < text.size() && p < pattern.size() )
    {
        if ( text[t] == pattern[p] ) {
            t++;
            p++;
        }
        else {
            t = /*   空白(a)   */;
            p = /*   空白(b)   */;
        }
    }

    if ( /*   空白(c)   */ )
        return /*   空白(d)   */;  // 何文字目に見つかったかを返す。
    else
        return text.size();        // 見つからなかった場合

}

課題２ Knuth-Morris-Pratt 法の next表

以下は Knuth-Morris-Pratt 法の next 表（失敗関数とも言う）を求めるプログラム である。これを用いて様々なパターンに対して、next 表を求めてみなさい。

このプログラムの内容は理解しなくて良い。 

void kmp_next_table( string & pattern, vector<int> & next )
{

    int t = 1;
    int p = 0;

    next[0]=0; next[1]=0;

    while( t < pattern.size() )
    {
        if ( pattern[t] == pattern[p] ) {
            t++;
            p++;
            if( t < pattern.size() )
               next[t] = p;
        }
        else {
            if ( p == 0 ) {
               t++;
               if( t < pattern.size() )
                  next[t] = 0;
            }
            else
               p = next[ p ];
        }
    }
}

課題 ３ Knuth-Morris-Pratt 法

以下は Knuth-Morris-Pratt 法による文字列探索プログラムである。

ここで用いられる next 表を 手作業で求める練習をしなさい。正しい next 表は課題２の プログラムで確認しなさい。 

int KnuthMorrisPratt( string & pattern, string & text )
{
    vector<int> next( pattern.size()  + 1  );  // 応急処置としてサイズを一つ大きくします。

    kmp_next_table( pattern, next );     // next 表の計算

    int t = 0;
    int p = 0;

    while( t < text.size() && p < pattern.size() )
    {
        if ( text[t] == pattern[p] ) {
            t++;
            p++;
        }
        else {
            if ( p == 0 ) 
               t++;
            else
               p = next[ p ];
        }
    }

    /* 以下は 力まかせ法と同じ */
}

課題 ４ 剰余演算の性質

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;               // high_factor = 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();
}