[BOJ]1786번: 찾기 (c++)

www.acmicpc.net/problem/1786

1786번: 찾기

 

KMP 문자열 알고리즘

#include <iostream>
#include <vector>

using namespace std;

// Prefix Index 배열 만들기
vector<int> make_pi(string &pattern)
{
    int len = pattern.size();
    vector<int> pi(len);

    for (int i = 1, j = 0; i < len; ++i)
    {
        while (j > 0 && pattern[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (pattern[i] == pattern[j])
        {
            pi[i] = ++j;
        }
    }
    return pi;
}

// kmp 알고리즘으로 parent에서 pattern이 등장하는 인덱스 배열 생성
vector<int> get_pattern_locations(string &parent, string &pattern)
{
    int str_len = parent.size();
    int pattern_len = pattern.size();
    vector<int> pi = make_pi(pattern);

    vector<int> locations;

    for (int i = 0, j = 0; i < str_len; ++i)
    {
        while (j > 0 && parent[i] != pattern[j])
        {
            j = pi[j - 1];
        }

        if (parent[i] == pattern[j])
        {
            ++j;

            // pattern이 모두 일치하면 처음 등장했던 idx를 locaitons에 push
            if (j == pattern_len)
            {
                locations.push_back(i - pattern_len + 1);
            }
        }
    }

    return locations;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 입력
    string parent, pattern;
    getline(cin, parent);
    getline(cin, pattern);

    // kmp 알고리즘으로 parent에서 pattern이 등장하는 인덱스 배열 생성
    vector<int> locations = get_pattern_locations(parent, pattern);

    // 출력
    cout << locations.size() << '\n';
    for (int location : locations)
    {
        cout << (location + 1) << ' ';
    }

    return 0;
}

 

 

문제가 정말 길다..!

하지만 미리 KMP알고리즘을 공부한 사람이라면

이 장황한 문제가 그냥 KMP를 (어지럽게) 설명하고 있을 뿐이라는 것을 금방 알 수 있다.

 

매칭은 T의 n-m+1번 문자에서까지 시작할 수 있으므로

그리고 친절하게도 요 인덱스 숫자를 배열에 저장하라고 알려주고 있다

// pattern이 모두 일치하면 처음 등장했던 idx를 locaitons에 push
if (j == pattern_len)
{
    locations.push_back(i - pattern_len + 1);
}

 

 

단, 출력에서 요구하는 인덱스는 0이 아니라 1부터 시작한다.

위의 값에서 1씩 더해서 출력하거나, 처음부터 1을 더해주자.