2014 Data Structures and Algorithms


コードを次のように変更してみよう。
  1. 検索対象の長い文字列(original_text)を、もっと長いもの(例えば、"That you don't want me there by your side. That you don't want me there in your life.")に変更してみよう。
#include <stdio.h>
#include <stdlib.h>
 
unsigned char original_text[] = "Team Swift";
unsigned char original_pattern[] = "if";
 
#define _SHOW_WORKING_
 
unsigned char *simple_search
                (unsigned char *text, unsigned char *pattern) {
    int i;
    while((*text) != '\0') {
#ifdef _SHOW_WORKING_
        /* わかりやすいように,いま何を比較しているか表示 */
        printf("    本文:%s \nパターン:", original_text);
        for(i = 0; i < text - original_text; i++) {
            printf(" ");
        }
        printf("%s \n", pattern);
#endif
 
        /* パターンの先頭から比較を始める */
        for(i = 0; pattern[i] != '\0'; i++) {
            if(pattern[i] != text[i]) {
                break;              /* 一致しなかった */
            }
        }
        if(pattern[i] == '\0') {        /* 一致した */
            return text;
        }
 
        /* 一致しなかったので,テキストを1つずらして再度挑戦 */
        text++;
    }
 
    return NULL;
}
 
int main(void) {
    unsigned char *result;
    result = simple_search(original_text, original_pattern);
    if(result == NULL) {
        printf("見つかりませんでした\n");
    } else {
        printf("見つかりました\n");
    }
 
    return EXIT_SUCCESS;
}



コードについて次のことを調べてみよう。
  1. list9-3.cと同じデータで動作確認してみよう。
  2. list9-3.cと実行時間に違いがあるか、同じデータ上でいろいろな文字列を検索して比較してみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define PATTERN_LENGTH 13
unsigned char original_text[] = "a eighty-eighty-eighth key";
unsigned char original_pattern[PATTERN_LENGTH + 1] = "eighty-eighth";
 
#define _SHOW_WORKING_
 
unsigned char *kmp_search
                    (unsigned char *text, unsigned char *pattern) {
    int table[PATTERN_LENGTH + 1] = {0, 0};
    int text_index = 1, pattern_index = 0;
    int i = 0, j;
 
    /* まずkmpの検索に必要な情報を集め,テーブルとして保存する */
    while((pattern[text_index]) != '\0') {
        if(pattern[text_index] == pattern[pattern_index]) {
        /* 一致したら再検索はpattern_index文字から始めればよい */
            table[++text_index] = ++pattern_index;
        } else if(pattern_index == 0) {
            /* パターン1文字目で不一致ならば,再検索は先頭から */
            table[++text_index] = 0;
        } else {
            /* パターン1文字目以外で不一致ならば,
               再検索の位置はtableから参照 */
            pattern_index = table[pattern_index];
        }
    }
    /* 以上でテーブルが完成,実際の検索にとりかかる */
 
    while((*text) != '\0') {
#ifdef _SHOW_WORKING_
        /* わかりやすいように,いま何を比較しているか表示 */
        printf("    本文:%s \nパターン:", original_text);
        for(j=0;j<text-original_text;++j) {
            printf(" ");
        }
        printf("%c \n", pattern[i]);
#endif
        if((*text) == pattern[i]) {
            /* テキストとパターンが一致していれば,
               1字ずつ比較を続ける */
            text++;
            if(pattern[++i] == '\0') {
                /* すべて一致すれば,正解 */
                return text - PATTERN_LENGTH;
            }
        }
        else if(i == 0) {
            /* パターン最初の文字で失敗した場合は,
               比較場所を1つ進める */
            text++;
        } else {
            /* 最初の文字でない場合は,
               テーブルから比較位置を取得する */
            i = table[i];
        }
    }
 
    return NULL;
}
 
int main(void) {
    unsigned char *result;
    result = kmp_search(original_text, original_pattern);
    if(result == NULL) {
        printf("見つかりませんでした\n");
    } else {
        printf("見つかりました\n");
    }
 
    return EXIT_SUCCESS;
}



コードを次のように変更してみよう。
  1. このファイルに含まれる文字列に"atggcc"という文字列が何回出てくるかを数えるように変更してみよう。
    • ソースコードの中に、上のファイルに入っている文字列を張り付けるのはダメです。プログラムの中で上のファイルを読むこと。
  2. 上のファイルから、ユーザが入力した任意の文字列を探せるようにしてみよう。
#include <stdio.h>
#include <stdlib.h>
 
#define PATTERN_LENGTH 4
unsigned char original_text[] = "On a dark desert highway, "
                                    "cool wind in my hair,";
unsigned char original_pattern[PATTERN_LENGTH + 1] = "wind";
 
#define _SHOW_WORKING_
 
unsigned char *bm_search(unsigned char *text,unsigned char *pattern) {
    /* char型全体について,その文字で一致しなかった場合, */
    /* どれだけ比較点を移動するかのテーブル */
    int table[256];
    /* 本文とパターンの比較点 */
    int text_index, pattern_index, text_len, i;
 
    for(i = 0; i < 256; i++) {
        /* たいていの文字は,失敗した場合,
           patternの長さぶん比較点をずらせばよい */
        table[i] = PATTERN_LENGTH;
    }
    for(i = 0; i < PATTERN_LENGTH - 1; i++) {
        /* パターンに含まれている文字はその文字に合わせてずらす
        パターンに同じ文字が含まれていた場合は後方の文字優先 */
        table[pattern[i]] = PATTERN_LENGTH - i - 1;
    }
 
    /* 本文の長さを知る */
    for(text_len=0;text[text_len]!='\0';++text_len)
        ;
 
    /* 最初の比較点は,テキストのパターン文字目から */
    text_index = PATTERN_LENGTH - 1;
 
    while(text_index < text_len) {
#ifdef _SHOW_WORKING_
        /* わかりやすいように,いま何を比較しているか表示 */
        printf("    本文:%s \nパターン:", original_text);
        for(i = 0; i < text_index - PATTERN_LENGTH + 1; i++) {
            printf(" ");
        }
        printf("%s \n", pattern);
#endif
        /* パターンの後ろから比較を始める */
        pattern_index = PATTERN_LENGTH - 1;
        while(text[text_index] == pattern[pattern_index]) {
            if(pattern_index==0) {
                /* パターンの先頭文字まで,すべて比較成功 */
                return text+text_index;
            }
            text_index--;
            pattern_index--;
        }
 
        if(table[text[text_index]] > PATTERN_LENGTH - pattern_index) {
            /* その文字に応じて,比較点を移動 */
            text_index += table[text[text_index]];
        } else {
            /* パターンが前にずれるのを防ぐ */
            /* 下の式はパターンを1つ後ろにずらしている */
            text_index += PATTERN_LENGTH - pattern_index;
        }
    }
 
    return NULL;
}
 
int main(void) {
    unsigned char *result;
    result = bm_search(original_text, original_pattern);
    if(result == NULL) {
        printf("見つかりませんでした\n");
    } else {
        printf("見つかりました\n");
    }
 
    return EXIT_SUCCESS;
}