[문자열 검사] Boyer_moore 알고리즘

[문자열 검사] Boyer_moore 알고리즘

#include <stdio.h>
 
char string[] = "a pattern matching algorithm";
char input[10] = "rithm";
int size, stringsize;
int skip[10];
 
int _strlen(char *str)    {
    int size = 0;
    while (*(str + size) != '\0')    size++;
    return size;
}
 
void makeskip()
{
    int i;
    for (i = 0; i <= size; i++)    {
        skip[i] = i;
    }
}
 
int boyer_moore()
{
    int i, j, idx;
 
    makeskip();
 
    for (idx = size - 1; idx < stringsize; )    {
        j = 0;
        while (j < size && string[idx - j] == input[size - 1 - j])    j++;
        if (j == size)    return idx - size + 1;
 
        i = idx - j;
        while (j < size && string[i] != input[size - 1 - j])    j++;
 
        idx += skip[j];
    }
 
    return -1;
}
 
int main()
{
    int index = 0;
    int i;
 
    stringsize = _strlen(string);
    size = _strlen(input);
 
    index = boyer_moore();
 
    if (index < 0)    printf("no exist\n");
    else {
        printf("%s\n%d - ", input, index);
        for (i = 0; i < size; i++)    {
            printf("%c", string[i + index]);
        }
        printf("\n");
    }
 
    return 0;
}