STEP 3.1

問題

実行例

[実行例] 
探したい文字列を入力してください :ababc
 t[0] = a
 t[1] = b
 t[2] = a
 t[3] = b
 t[4] = d
 t[5] = a
 t[6] = b
 t[7] = a
 t[8] = b
 t[9] = c
 t[10] = c
 t[11] = b
 t[12] = d
 t[13] = c
 t[14] = a
 t[15] = b
 t[16] = c
 t[17] = a
 t[18] = d
 t[19] = b
 Pattern ababc is matched at 5


探したい文字列を入力してください :tsuchiya
 t[0] = a
 t[1] = b
 t[2] = a
 t[3] = b
 t[4] = d
 t[5] = a
 t[6] = b
 t[7] = a
 t[8] = b
 t[9] = c
 t[10] = c
 t[11] = b
 t[12] = d
 t[13] = c
 t[14] = a
 t[15] = b
 t[16] = c
 t[17] = a
 t[18] = d
 t[19] = b
 Pattern tsuchiya is not found

コメント

  1. テキストを左から順に。パターンの最初の1文字が同じところがあったら、パターンの残りの文字をチェック。
  2. 残りの文字の途中でダメになったら、テキストについて、またパターンの1文字目のチェックへ戻る。
  • 下のプログラム例では、読み込みにscanfを使っているので、空白やタブは、入力できない。空白などを使用したい場合はgetsを利用のこと (Cの絵本 p120)
  • getsは、バッファーオーバーフロー（予定されている文字数以上の入力が行われる場合）にうまく対応できないので、fgetsを利用する (Cの絵本 p110)
  • 解答のプログラムで、fgetsに置き換えたものを示す。
  • テキストもscanfしたい人は、プログラム例を参考に
  • Visual Studioの皆さん - 1行目に#define _CRT_SECURE_NO_WARNINGSと書くと、scanfへの警告を停止 (本来はすべきではありません)
  1. カウンターを追加しよう。 
    探したい文字列を入力してください :ababc
t[0] = a
t[1] = b
t[2] = a
t[3] = b
t[4] = d
t[5] = a
t[6] = b
t[7] = a
t[8] = b
t[9] = c
t[10] = c
t[11] = b
t[12] = d
t[13] = c
t[14] = a
t[15] = b
t[16] = c
t[17] = a
t[18] = d
t[19] = b
cnt = 16 (←　比較回数をカウントする変数cntを追加、比較回数を表示。p.100 図5.3 )
Pattern ababc is matched at 5
  2. ひどい例を考えてみよう。どんなテキストに、どんなパターンの場合だろうか。実行させてみよう。（p.102 下を参考に）
  3. このアルゴリズムの計算量を考えよう。（O記法で表現する）
    • nをテキストの長さ、mをパターンの長さとして、考えよう。
    • 処理対象のmとnが大きくなると、このアルゴリズムの計算時間（最悪の場合）はどのように増加するかを分析しよう。

解答例

[解答例（未完）]

例題集 


#include <stdio.h>
#include <string.h> /*　文字関係のライブラリ よくわかるC p71 */

/* プロトタイプ宣言 */
void print_text(char []); /* 文字列配列tの表示 */
int naive(char [], char []); /* 引数は文字の配列。別の書き方もある */


int main (void) {
    char t[30]; /* 文字列の最後は \0 ヌル文字なので、最大29文字 */
    char p[10];
    int j; /* 戻り値をうけとる変数 マッチするなら、配列tの添え字 */

    /* テキストは、教科書の例 p.98 */
    strcpy(t, "ababdababccbdcabcadb"); /* 文字列の代入 よくわかるC p68 */

    /* テキストを、入力させるようにするなら、上をやめて、下のように
    printf("文字列を入力してください :");
    scanf("%s", t);
    */

    /* パターンは入力 p.98 */
    printf("探したい文字列を入力してください :");
    scanf("%s", p);

    print_text(t);    /* テキストの出力 */
    j = naive(t,p);   /* 素朴、力づく、力まかせのアルゴリズム実装 */

    /* 戻り値に応じて、出力文 */
    if (j == -1) /* 見つからない */
        printf("Pattern %s is not found \n", p);
    else /* テキスト配列tの添え字jから見つかった */
        printf("Pattern %s is matched at %d \n", p,j);

    return 0;
}

/* この関数を、完成させよう */
int naive (char t[], char p[]){
    int i = 0;
    int j = 0;
    int m = strlen(p); /* 文字列の長さ よくわかるC p71 文字列操作関数 */
    int n = strlen(t);

  


   /* 手続き 疑似コードも参考にしてよい。完成させてください。全体を、よく読み、納得すること*/

   /* なぞり ←→　アルゴリズムとして言葉で整理　←→　プログラムコード */
    　　　　　　　/*  プログラムツールへ (見たら、かなりヒントになります）（最後のアンケートにご協力を) */

    /* printf 文を差し込むなどして、変数の状態を出力、確認してみるとよい */
    while (



    if (i == m)
       return (j - i);
    else
       return (-1);

}

/* 文字列の最後には\0 ヌル記号。例題集 5の定番処理です */
/* strlenで文字列のサイズを得て、ループする方法もある */
/* よくわかるC言語 p65 は forループで。以下はwhileループ版 */
void print_text(char t[]) {
    int j = 0;
    while (t[j] != '\0') {  /* 最後のヌル文字ではない */
        printf("t[%d] = %c\n", j, t[j]); /* 1文字をプリント */
        j++;
    }
}