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

演習8-9の解答

0 ABABCDEFGHA
  +
  ABC

  ABABCDEFGHA
   +
  ABC

  ABABCDEFGHA
    |
  ABC

1 ABABCDEFGHA
   |
   ABC
　(中略)
比較は7回でした。

　探索の過程が視覚的に分かるように、右のような出力を行うプログラムを作成せよ。
　すなわち、パターンを移動するたびに、照合するテキスト側の先頭文字の添字を表示すること。
　また、照合の過程を表示する際は、比較する二つの文字間に一致すれば文字'+'を、一致しなければ文字'|'を表示すること。
　なお、最後に文字を比較した総回数を表示すること。

/*
    演習8-9
    力まかせ法による文字列探索
*/

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

/*--- 力まかせ法による文字列探索 ---*/
int bf_match(const char txt[], const char pat[])
{
    int  i, k = -1;
    int  count = 0;
    int  tlen = strlen(txt);
    int  plen = strlen(pat);
    int  pt = 0;        /* txtをなぞるカーソル */
    int  pp = 0;        /* patをなぞるカーソル */

    while (txt[pt] != '\0'  &&  pat[pp] != '\0') {
        if (k == pt - pp)
            printf("    ");
        else {
            printf("%2d  ", pt - pp);
            k = pt - pp;
        } 
        for (i = 0; i < tlen; i++)
            printf("%c ", txt[i]);
        putchar('\n');

        printf("%*s%c\n", pt*2+4, "", (txt[pt] == pat[pp]) ? '+' : '|');

        printf("%*s", (pt-pp)*2+4, "");
        for (i = 0; i < plen; i++)
            printf("%c ", pat[i]);
        printf("\n\n");
        count++;

        if (txt[pt] == pat[pp]) {
            pt++;
            pp++;
        } else {
            pt = pt - pp + 1;
            pp = 0;
        }
    }

    printf("比較は%d回でした。\n", count);
    if (pat[pp] == '\0')
        return (pt - pp);
    return (-1);
}

int main(void)
{
    int   idx;
    char  s1[80];       /* テキスト */
    char  s2[80];       /* パターン */

    printf("テキスト：");
    scanf("%s", s1);

    printf("パターン：");
    scanf("%s", s2);

    idx = bf_match(s1, s2);     /* 文字列s1から文字列s2を力まかせ法で探索 */

    if (idx == -1)
        puts("テキスト中にパターンは存在しません。");
    else
        printf("%d文字目に見つかりました。\n", idx + 1);

    return (0);
}

戻る