[문자열 검사] 카프-라빈 알고리즘

[문자열 검사] 카프-라빈 알고리즘

// 해시 값 함수를 이용
#include <stdio.h>
 
char string[] = "hello my name is ksj";
char input[10];
int size;
int strhash[30];
int inputhash;
 
int _strlen(char *str)    {
    int size = 0;
    while (*(str + size) != '\0')    size++;
    return size;
}
 
void makeHash()
{
    int i;
    int h = 0;
    char c;
    int temp = 1;
 
    inputhash = 0;
    for (i = 0; i < size; i++)    {
        c = string[i];
        h *= 10;
        inputhash *= 10;
        temp *= 10;
 
        if (c >= 'a' && c <= 'z')    h += c - 'a';
        else if (c >= 'A' && c <= 'Z')    h += c - 'A';
        else h += c - ' ';
 
        c = input[i];
        if (c >= 'a' && c <= 'z')    inputhash += c - 'a';
        else if (c >= 'A' && c <= 'Z')    inputhash += c - 'A';
        else inputhash += c - ' ';
    }
    strhash[0] = h;
    temp /= 10;
 
    for (i = 1; string[i + size - 1] != '\0'; i++)    {
        c = string[i - 1];
        if (c >= 'a' && c <= 'z')    c -= 'a';
        else if (c >= 'A' && c <= 'Z')    c -= 'A';
        else c -= ' ';
        h = (h - c * temp) * 10;
 
        c = string[i + size - 1];
        if (c >= 'a' && c <= 'z')    h += c - 'a';
        else if (c >= 'A' && c <= 'Z')    h += c - 'A';
        else h += c - ' ';
        strhash[i] = h;
    }
}
 
int compare()
{
    int i, j;
 
    for (i = 0; string[i + size - 1] != '\0'; i++)    {
        if (strhash[i] == inputhash)    {
            for (j = 0; j < size; j++)    {
                if (string[i + j] != input[j])    {
                    break;
                }
            }
            if (input[j] == '\0')    {
                return i;
            }
        }
    }
 
    return -1;
}
 
int main()
{
    int index;
    int i;
 
    scanf("%s", input);
    size = _strlen(input);
 
    makeHash();
 
    index = compare();
 
    if (index < 0)    printf("no exist\n");
    else {
        printf("%d - ", index);
        for (i = 0; i < size; i++)    {
            printf("%c", string[i + index]);
        }
        printf("\n");
    }
 
    return 0;
}