KMPアルゴリズムによるパターン検索

本記事では、KMP(Knuth-Morris-Pratt)アルゴリズムを用いたファイル内文字列検索の実装について説明します。この実装はfindstrコマンドのような機能を提供し、ディレクトリの再帰的な走査やパターンマッチングを含みます。

ヘッダーファイル (findstr.h)

#ifndef _FIND_STR_H_
#define _FIND_STR_H_

#ifdef __cplusplus
extern "C" {
#endif

#include <stdio.h>

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

#define E_OK 0
#define E_FAIL -1

typedef void *line_callback(char *line, size_t len, int linum, void *param);
typedef int file_callback(const char *path, line_callback fn, void *param);

off_t findstr(const char *text, size_t len, const char *pattern, size_t n);
off_t kmp_search(const char *str, size_t sl, const char *match, size_t ml);
int process_file_lines(const char *path, line_callback fn, void *param);
int scan_directory(const char *dirPath, file_callback fn, void *param);
int is_directory(const char *path);
char *trim_right(char *str, const char *chs);
void *add_line_number(char *line, size_t len, int num, void *param);
int scan_directory_recursive(const char *dirPath, file_callback fn, void *param);

#ifdef __cplusplus
}
#endif

#endif

実装ファイル (findstr.c)

#include "findstr.h"
#include <string.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <errno.h>
#include "queue.h"
#include <stdlib.h>

off_t findstr(const char *text, size_t len, const char *pattern, size_t n) {
    char *sub = strstr(text, pattern);
    return sub ? (off_t)(sub - text) : -1;
}

int scan_directory(const char *dirPath, file_callback fn, void *param) {
    DIR *dir = opendir(dirPath);
    if (!dir) {
        if (errno == ENOTDIR) return errno;
        return errno;
    }

    char path[256];
    struct dirent *entry;
    while ((entry = readdir(dir))) {
        if (!strcmp(entry->d_name, ".") || !strcmp(entry->d_name, "..")) continue;

        snprintf(path, sizeof(path), "%s/%s", dirPath, entry->d_name);
        if (entry->d_type == DT_DIR) {
            printf("d ");
        } else {
            printf("- ");
            if (fn) fn(path, NULL, param);
        }
        printf("%s\n", path);
    }
    closedir(dir);
    return 0;
}

int is_directory(const char *path) {
    struct stat st;
    if (!strncmp(path, "stdin", 5)) return FALSE;
    if (stat(path, &st)) return FALSE;
    return S_ISDIR(st.st_mode);
}

int is_regular_file(const char *path) {
    struct stat st;
    if (!strncmp(path, "stdin", 5)) return TRUE;
    if (stat(path, &st)) return FALSE;
    return S_ISREG(st.st_mode) || S_ISCHR(st.st_mode);
}

int process_file_lines(const char *path, line_callback fn, void *param) {
    FILE *fp = !strncmp(path, "stdin", 6) ? stdin : fopen(path, "r");
    if (!fp) return errno;

    char line[1024];
    int num = 0;
    size_t match_found = 0;
    while (fgets(line, sizeof(line), fp)) {
        num++;
        match_found |= (size_t)fn(line, strlen(line)+1, num, param);
    }

    if (match_found) printf("%s\n", path);
    if (fp != stdin) fclose(fp);
    return E_OK;
}

char *trim_right(char *str, const char *chs) {
    if (!str) return NULL;
    char *ptr = str + strlen(str) - 1;
    
    if (!chs) {
        while (ptr >= str && (*ptr == ' ' || *ptr == '\t' || *ptr == '\r' || *ptr == '\n')) {
            *ptr-- = '\0';
        }
    } else {
        while (ptr >= str) {
            const char *t;
            for (t = chs; *t; t++) {
                if (*ptr == *t) break;
            }
            if (!*t) break;
            *ptr-- = '\0';
        }
    }
    return str;
}

extern char SearchPattern[64];

void *add_line_number(char *line, size_t len, int num, void *param) {
    off_t offset = kmp_search(line, len, SearchPattern, strlen(SearchPattern));
    if (offset < 0) return NULL;

    line[len-1] = '\0';
    char buf[16];
    char *p = &buf[sizeof(buf)-1];
    *p-- = '\0';
    *p-- = ' ';
    *p = ':';

    while (num) {
        *--p = '0' + (num % 10);
        num /= 10;
    }
    fputs(p, stdout);
    fputs(line, stdout);
    return p;
}

struct dir_entry {
    char path[256];
    SIMPLEQ_ENTRY(dir_entry) entries;
};

int scan_directory_recursive(const char *dirPath, file_callback fn, void *param) {
    DIR *dir = opendir(dirPath);
    if (!dir) return errno;

    SIMPLEQ_HEAD(, dir_entry) queue;
    SIMPLEQ_INIT(&queue);

    struct dir_entry *entry = malloc(sizeof(*entry));
    strncpy(entry->path, dirPath, sizeof(entry->path));
    SIMPLEQ_INSERT_HEAD(&queue, entry, entries);

    while (!SIMPLEQ_EMPTY(&queue)) {
        entry = SIMPLEQ_FIRST(&queue);
        DIR *subdir = opendir(entry->path);
        if (!subdir) {
            free(entry);
            continue;
        }

        struct dirent *pd;
        while ((pd = readdir(subdir))) {
            if (!strcmp(pd->d_name, ".") || !strcmp(pd->d_name, "..")) continue;

            char full_path[256];
            snprintf(full_path, sizeof(full_path), "%s/%s", entry->path, pd->d_name);

            if (pd->d_type == DT_DIR) {
                struct dir_entry *new_entry = malloc(sizeof(*new_entry));
                strncpy(new_entry->path, full_path, sizeof(new_entry->path));
                SIMPLEQ_INSERT_TAIL(&queue, new_entry, entries);
            } else {
                if (fn) fn(full_path, add_line_number, NULL);
            }
        }
        closedir(subdir);
        free(entry);
    }
    closedir(dir);
    return 0;
}

int *create_failure_function(const char *pattern, size_t len) {
    int *table = malloc(len * sizeof(int));
    if (len == 0) return table;

    table[0] = -1;
    if (len == 1) return table;

    table[1] = 0;
    size_t pos = 2;
    int candidate = 0;

    while (pos < len) {
        if (pattern[pos-1] == pattern[candidate]) {
            table[pos++] = ++candidate;
        } else if (candidate > 0) {
            candidate = table[candidate];
        } else {
            table[pos++] = 0;
        }
    }
    return table;
}

off_t kmp_search(const char *text, size_t text_len, const char *pattern, size_t pattern_len) {
    if (pattern_len == 0 || text_len < pattern_len) return -1;

    int *table = create_failure_function(pattern, pattern_len);
    size_t i = 0, j = 0;

    while (i < text_len && j < pattern_len) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        } else if (table[j] == -1) {
            i++;
        } else {
            j = table[j];
        }
    }

    off_t result = (j == pattern_len) ? (i - j) : -1;
    free(table);
    return result;
}

メイン関数 (main.c)

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

char SearchPattern[64];

int main(int argc, char *argv[]) {
    char path[256];
    
    if (argc < 2) {
        printf("Usage: %s pattern [file_path]\n", argv[0]);
        return 0;
    }

    strncpy(SearchPattern, argv[1], sizeof(SearchPattern));
    if (argc < 3) {
        strcpy(path, "stdin");
    } else {
        strncpy(path, argv[2], sizeof(path));
    }

    trim_right(path, "\\/ ");
    printf("-- Searching in %s -- \n", path);

    if (is_directory(path)) {
        scan_directory_recursive(path, process_file_lines, NULL);
    } else {
        process_file_lines(path, add_line_number, NULL);
    }
    
    return 0;
}