BohYoh.comトップページへ

C言語によるアルゴリズムとデータ構造

戻る  

演習8-12の解答

 関数kmp_match を以下の形式にしたものを作成せよ。返却するのは一致した文字の添字ではなく、その文字へのポインタとすること。また、探索に失敗した場合は空ポインタを返すこと。
  char *kmp_match (const char *txt , const char *pat );

/* 演習8-12 KMP法による文字列探索 */ #include <stdio.h> /*--- KMP法による文字列探索 ---*/ char *kmp_match(const char *txt, const char *pat) { int pt = 1; /* txtをなぞるカーソル */ int pp = 0; /* patをなぞるカーソル */ int skip[1024]; /* スキップテーブル */ skip[pt] = 0; while (pat[pt] != '\0') { if (pat[pt] == pat[pp]) skip[++pt] = ++pp; else if (pp == 0) skip[++pt] = pp; else pp = skip[pp]; } pt = pp = 0; while (txt[pt] != '\0' && pat[pp] != '\0') { if (txt[pt] == pat[pp]) { pt++; pp++; } else if (pp == 0) pt++; else pp = skip[pp]; } if (pat[pp] == '\0') return (txt + pt - pp); return (NULL); } int main(void) { char *idx; char s1[80]; /* テキスト */ char s2[80]; /* パターン */ printf("テキスト:"); scanf("%s", s1); printf("パターン:"); scanf("%s", s2); idx = kmp_match(s1, s2); /* 文字列s1から文字列s2をKMP法で探索 */ if (idx == NULL) puts("テキスト中にパターンは存在しません。"); else printf("%d文字目に見つかりました。\n", idx - s1 + 1); return (0); }


戻る