[알고리즘] KMP

KMP 알고리즘

참고

http://bowbowbow.tistory.com/6

snippet

void getPi(char* Pattern)
{
    int i = 1;
    int j = 0;

    int len = mstrlen(Pattern);

    while (i<len)
    {

        if (Pattern[i] == Pattern[j])
        {
            pi[i] = ++j;
            i++;
        }
        else
        {
            if (j == 0)
            {
                i++;
            }
            else
            {
                j = pi[j - 1];
            }
        }
    }
}

 

 

solution

//http://bowbowbow.tistory.com/6

#include<stdio.h>

#define MAXN (512)

int Border[MAXN];

int pi[MAXN];

inline int mstrlen(char* a)
{
    int i = 0;
    for (; a[i]; i++);
    return i;
}

void getPi(char* Pattern)
{
    int i = 1;
    int j = 0;

    int len = mstrlen(Pattern);

    while (i<len)
    {

        if (Pattern[i] == Pattern[j])
        {
            pi[i] = ++j;
            i++;
        }
        else
        {
            if (j == 0)
            {
                i++;
            }
            else
            {
                j = pi[j - 1];
            }
        }
    }

}

int getPatter(char* Pattern, char* Target)
{
    int i = 0;
    int j = 0;
    int ret = 0;

    int len = mstrlen(Target);

    while (i < len)
    {

        if (Target[i] == Pattern[j])
        {
            if (ret == 0) ret = i;

            i++;
            j++;
        }
        else
        {
            if (j == 0)
            {
                i++;
                ret = 0;
            }
            else
            {
                j = pi[j - 1];
                ret = 0;
            }
        }
    }

    return ret;
}

int main(void)
{
    char Text[] = "ABABABABBABABABABC";
    char Pattern[] = "ABABABABC";

    getPi(Pattern);

    int ret = getPatter(Pattern, Text);

    return 0;
}