| テキスト文字列txt からパターン文字列pat を探索する以下の関数を作成せよ。最も末尾側に出現する位置を探索すること。 返却するのは、一致したテキスト側の先頭文字へのポインタとする。ただし、探索に失敗した場合は空ポインタを返すこと。 char *strrstr (const char *txt , const char *pat ); |
/* 演習8-14 Boyer-Moore法による文字列探索（末尾側の一致を探す） */ #include <stdio.h> #include <string.h> #include <limits.h> /*--- Boyer-Moore法による文字列探索（末尾側の一致を探す） ---*/ char *strrstr(const char *txt, const char *pat) { int i; int pt; /* txtをなぞるカーソル */ int pp; /* patをなぞるカーソル */ int txt_len = strlen(txt); /* txtの文字数 */ int pat_len = strlen(pat); /* patの文字数 */ int skip[UCHAR_MAX + 1]; /* スキップテーブル */ for (pt = 0; pt <= UCHAR_MAX; pt++) /* スキップテーブルの作成 */ skip[pt] = pat_len; for (pt = pat_len - 1; pt > 0; pt--) skip[pat[pt]] = pt; pt = txt_len - pat_len; while (pt >= 0) { pp = 0; /* patの先頭文字に着目 */ while (txt[pt] == pat[pp]) { if (pp == pat_len - 1) return (txt + pt - pat_len); pp++; pt++; } pt -= skip[txt[pt]]; } return (NULL); } int main(void) { char* idx; char s1[80]; /* テキスト */ char s2[80]; /* パターン */ printf("テキスト："); scanf("%s", s1); printf("パターン："); scanf("%s", s2); idx = strrstr(s1, s2); /* 文字列s1から文字列s2をBoyer-Moore法で探索 */ if (idx == NULL) puts("テキスト中にパターンは存在しません。"); else printf("%d文字目に見つかりました。\n", idx - s1 + 1); return (0); }
