(C++) - KMP 알고리즘

문제링크  https://www.acmicpc.net/problem/1786

1786번: 찾기

KMP문제입니다

아래 소스코드는 KMP설명을 위해 저 문제의 답을 예시로 적었습니다.

p는 찾으려는 문자열 s는 주어지는 문자열

 

KMP Algorithm

1. 시간 복잡도 O(n+m) - > pi배열을 만드는 시간 m(원하는 문자열의 길이), 주어진 문자열에서 원하는 문자열 찾는 시간 n

 

2. Preprocessing - > pi배열 만들기 : 찾길 원하는 문자열은 p,주어진 문자열을 s라 했을 때,

 1) p의 접두사와, 접미사를 비교하여 p의 인덱스 마다 그 둘이 같은 것의 길이를 저장한다,같지 않으면 pi[i]=0

 2) while문을 pi의 인덱스가 하나 증가할 때마다 돌린다(line 28) -> 현재 p[i]의 문자가 그 전 문자들 중 하나와 같을때까지 pi배열을 검색
3) 현재 문자와 그 전 문자가 같다면 j++, pi에 j 대입

 

3. KMP -> Preprocessing과정에서 만든 pi배열을 전달 받는다

 1) while문 (line 48) - > s의 문자중 p의 문자와 같은 것을 찾는다 -> pi의 인덱스를 살펴보면 됨 

-> pi배열은 p배열의 접두,접미사가 p의 현재 문자에서 얼마나 같은지 저장되어있기 때문.

2) 그러므로 s와 p가 다르다면 다시 p의 처음부터 s와 비교할 필요없이 s는 계속하여 다음 문자를 pi배열과 비교하면 된다

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector <int> preprocessing(string p) {
    int psize = p.size();
    vector <int> pi(psize);
    pi[0] = 0;
    int j = 0;
    for (int i = 1; i < psize; i++)
    {
        while (j > 0 && p[i] != p[j])
        {
            j = pi[j - 1];
        }
        if (p[i] == p[j])
        {
            pi[i] = j + 1;
            j++;
        }
        else
            pi[i] = 0;
    }
    return pi;
}
vector <int> kmp(string s,string p)
{
    auto pi = preprocessing(p);
    vector <int> ans;
    int psize = p.size();
    int ssize = s.size();
    int j = 0;
    for (int i = 0; i < ssize; i++)
    {
        while (j > 0 && s[i] != p[j])//s는 전체 문자열, p는 찾으려는 문자열
        {
            j = pi[j - 1];
        }
        if (s[i] == p[j])
        {
            if (j == psize - 1)//마지막 문자열까지 같다면
            {
                ans.push_back(i - psize + 1);//위치를 저장
                j = pi[j];
            }
            else
                j += 1;
        }
    }
    return ans;
}
int main() {
    string s, p;
    getline(cin, s);
    getline(cin, p);
    auto matched = kmp(s, p);
    cout << matched.size() << '\n';
    for (auto index : matched)
        cout << index + 1 << ' ';
    cout << '\n';
}
​