KMP 알고리즘

문자열의 접두사와 접미사 부분을 비교해서 점프해주는 KMP 알고리즘

#include <stdio.h>
int T, N;
int tc;

char str[500000];
char ptr[100000];

int fail[100000];
int p_num;
int s_num;

//fail 함수 //
void find_pi(){
    int i, j;
    int k = 0;

    fail[0] = 0;

    for (i = 1; i < p_num; i++){

        while (k && ptr[k] != ptr[i]) {
            k= fail[k-1] ;
        }

        if (ptr[k] == ptr[i]) k++;

        fail[i] = k;
    }

}

//비교 함수 //
int comp(char *str_p, char *ptr_p){
   
    int i, j;
    int k = 0;
    int answer = 0;

    for (int i = 0; i < s_num ; i++){
        while (k && ptr[k] != str[i]) k = fail[k-1];

        if (ptr[k] == str[i]) k++;

        if (k == p_num)    {
            answer++;
            k = fail[k-1];
        }
    }
    return answer;

}