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

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

#include <stdio.h>
 
char string[] = "naabcdabcdefmeaabcdabcefksj";
char input[10] = "abcdabcef";
int next[50];
int size, stringsize;
 
int _strlen(char *str)    {
    int size = 0;
    while (*(str + size) != '\0')    size++;
    return size;
}
 
void makenext()
{
    int i;
 
    next[0] = 0;
    next[1] = 0;
 
    for (i = 2; i < size; i++)    {
        if (input[next[i - 1]] == input[i - 1])    {
            next[i] = next[i - 1] + 1;
        }
        else next[i] = 0;
    }
}
 
int kmp()
{
    int i, j;
    for (i = 0, j = 0; i < stringsize && j < size;)    {
        if (string[i] != input[j]) {
            if (j == 0)        i++;
            else            j = next[j];
        }
        else    {
            i++;
            j++;
        }
    }
    if (j == size)    {
        return i - size;
    }
    return -1;
}
 
int main()
{
    int index = 0;
    int i;
 
    stringsize = _strlen(string);
//    scanf("%s", input);
    size = _strlen(input);
 
    makenext();
 
    index = kmp();
 
    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;
}