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

演習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);
}

戻る