K&Rを読もう(28) 問題2-5 文字のマッチング

GCC

2-4より先に2-5をやる。

文字列のマッチングをして、一致する文字の位置を返す問題。

mixi時代にkusakabeさんに激しく突っ込まれたのでよく覚えてる。

#include <stdio.h>
#include <stdlib.h>

int any(char *s, char *match)
{
    int i = 0;
    char *sp;
    char *mp;
    for (;*s != '\0'; s++, i++) {
        if (*s == *match) {
            sp = s;
            mp = match;
            for (;*sp == *mp; sp++, mp++)
                ;
            if (*mp == '\0')
                return i;
        }
    }
    return -1;
}

int main(void)
{
    printf("%d\n", any("01234567", "345"));  /* 3 */
    printf("%d\n", any("bababcab", "babc")); /* 2 (凶悪なパターン) */
    printf("%d\n", any("", "abc"));          /* -1 */
    printf("%d\n", any("abcdefgh", ""));     /* -1 */
    
    exit(EXIT_SUCCESS);
}

kusakabeさんって口は悪いけどいい人。

exit(EXIT_SUCCESS)はkusakabeさんの影響です。うふ。

  • 先頭ポインタを保存しておかなければならないので、配列を使った方がわかりやすかったかも。
  • 同じような文字が続いた時の処理があるので、文字列マッチのアルゴリズムを適用しない場合、頭から1つづつチェックする必要がある。
  • ステップ数は「入力文字*マッチ文字」なので、長い文字列を比較すると膨大なステップ数が必要となる。

todo

BM法を使ったアルゴリズムをちゃんと覚える。

mixi

mixi CとC++ | そんなことおしえてねーよ!
ガーンまた突っ込まれてしまった・・・exit(EXIT_SUCCESS)は、return EXIT_SUCCESSと書くのが普通らしい。

どうやら、kusakabeさんの影響では無いらしい・・・。