STEP 3.1 B

<問題> 対象の文字列(テキスト)中に、探したい文字列(パターン)が含まれているかどうかを調べよう。(力ずくのアルゴリズムをプログラムしよう)
(STEP3.1 Aの解答と違い、入力にfgetsを使っています。実行例が変わっています)

<実行結果> 

文字列を入力してください :uma ga umattayo.
探したい文字列を入力してください :umatta
t[0] = u
t[1] = m
t[2] = a
t[3] =
t[4] = g
t[5] = a
t[6] =
t[7] = u
t[8] = m
t[9] = a
t[10] = t
t[11] = t
t[12] = a
t[13] = y
t[14] = o
t[15] = .
Pattern umatta is matched at 7

文字列を入力してください :AAKB
探したい文字列を入力してください :AKB
t[0] = A
t[1] = A
t[2] = K
t[3] = B
Pattern AKB is matched at 1

文字列を入力してください :uma ga umattenai
探したい文字列を入力してください :umatta
t[0] = u
t[1] = m
t[2] = a
t[3] =
t[4] = g
t[5] = a
t[6] =
t[7] = u
t[8] = m
t[9] = a
t[10] = t
t[11] = t
t[12] = e
t[13] = n
t[14] = a
t[15] = i
Pattern umatta is not found

<ヒント>

例題集へ



解答例

#include <stdio.h>
#include <string.h>

#define TEXTL 50 /* 改行まで */
#define PATL 20
/* プロトタイプ宣言 */
void print_text(char []); /* 文字列配列tの表示 */
int naive(char [], char []); /* 引数は文字の配列。別の書き方もある */

int main (void) {
    char t[TEXTL];
    char p[PATL];
    char *pp; /* 文字を操作するためのポインター */
    int j;

    printf("文字列を入力してください :");
    fgets(t, TEXTL, stdin);  /* TEXTL文字分しか読まない。ファイル名stdinは標準入 力のこと。ここではキーボード */
    pp = strchr(t, '\n'); /* fgetsでは、改行文字が残る。*/
    *pp = '\0';  /* その文字を、ヌル文字に置き換える */
    /* 本来入力部分は、TEXTLを超えて入力された場合の対処なども用意 */

    printf("探したい文字列を入力してください :");
    fgets(p, PATL, stdin);
    pp = strchr(p, '\n');
    *pp = '\0';

    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;
    while (t[j] != '\0' &&  p[i] != '\0') { /* どちらかがヌルになってしまったら終了. どんな論理式? */
         if (p[i] == t[j]) {  /* 一致している */
             i = i + 1;
             j = j + 1;
         } else { /* 一致しない */
             j = j - i + 1;
             i = 0;
         }
    }

    /* どちらかがヌルなら終了。ではpが含まれていて終了した場合か、どうかを調べよ う */
    if (p[i] == '\0')
        return (j - i);
    else
        return (-1);

}

void print_text(char t[]) {
    int j = 0;
    /* 定番の出力プログラム */
    while (t[j] != '\0') {
        printf("t[%d] = %c\n", j, t[j]);
        j++;
    }
}