KMP 알고리즘

https://www.youtube.com/watch?v=KXolmVUpUQQ 

 

 

#include <bits/stdc++.h>
using namespace std;

#define STR_LEN 100

//인 수: 패턴문자열
//반환:lps 배열

int* calculate_lps(char* _pattern_str){
    int pattern_len;
    int* _lps = 0; //LPS 배 열
    int i,j;

    pattern_len = strlen(_pattern_str);

    // LPS 배열
    _lps = (int *)malloc(sizeof(int)* pattern_len);

    // LPS 배열초기화
    memset(_lps, 0 , sizeof(int)*pattern_len);

    /*
     LPS 배열 계산
     */

    j = 0;

    for(int i=1; i<pattern_len; i++){
        if(j>0 && _pattern_str[i]!=_pattern_str[j]){
            j = _lps[j-1];
        }


        if(_pattern_str[i]==_pattern_str[j]){
            j++;
            _lps[i] = j;
        }
    }

    return _lps;
}


int main() {
    int i, j;

    //target string
    char target_str[STR_LEN] = "ABABABABBABABABABCABABABABBABABABABCABABABABBABABABABCABABABABBABABABABC";

    //pattern string
    char pattern_str[STR_LEN] = "ABABABABC";

    int target_len;
    int pattern_len;

    target_len = strlen(target_str);
    pattern_len = strlen(pattern_str);
    int* lps = 0;

    lps = calculate_lps(pattern_str);

    for(i = 0; i< pattern_len; i++){
        cout << i << ' ' << lps[i] << '\n';
    }


    // --- string matching

    printf("------------ start string matching of %s to %s\n", pattern_str, target_str);


    // i : target str의 현재위치 index
    // j : pattern str의 현재위치 index

    j = 0;

    for(i = 0; i< target_len; i++){
        while(j>0 && target_str[i] != pattern_str[j]){
            j = lps[j-1];
        }
        
        if(target_str[i] == pattern_str[j]){
            if(j == (pattern_len - 1)){
                cout << "Found matching at " << i - pattern_len + 1 << '\n';
                j = 0;
            }
            else{
                j++;
            }
        }
    }



    return 0;
}