KMP 알고리즘 수정

https://yiyj1030.tistory.com/495

[알고리즘/ 파이썬] KMP 알고리즘 알아보기

 

KMP 알고리즘을 구현하였는데 수정해야할 사항이 있었다.

 

사실 내가 구현한 코드는 KMP 알고리즘이라고 할 수 없다.

 

왜 그런지는 정확하게 설명할 수 없지만 KMP 알고리즘을 사용하지 않았다.

 

KMP 알고리즘의 패턴 테이블을 참조하여 중복 건너뛰기만 한 느낌이다.

 

일단 KMP 알고리즘이 정확하게 이해되지 않는 부분이

 

접두부의 인덱스를 패턴 테이블을 참조하여 이동하는 부분이었다.

 

위 글을 보며 계속해서 이해가 되고있는 중인데 아직 완벽하게 이해 되진 않는다.

 

vector<int> KMP(string p, string T) {
    vector<int> find;

    vector<int> pi = makepi(p);
    /*
    for (int i = 0; i < T.size() - p.size(); i++) {
        for (int j = 0; j < p.size(); j++) {
            if (p[j] != T[i + j]) {
                i = pi[j] + i;
                break;
            }
            if (j + 1 == p.size()) {
                find.push_back(i);
            }
        }
    }
    */

    int i = 0;
    int j = 0;

    while (i < T.size()) {
        if (p[j] == T[i]) {
            i++;
            j++;
        }
        if (j == p.size()) {
            find.push_back(i - j);
            j = pi[j - 1];
        }
        else if (i < T.size() && p[j] != T[i]) {
            if (j != 0) {
                j = pi[j - 1];
            }
            else {
                i++;
            }
        }
    }

    return find;
}

KMP 실행 부분을 수정하였다.