백준/1786번/찾기/플래티넘5

Problem Link: https://www.acmicpc.net/problem/1786

문제 설명

Site: Baekjoon
Number: 1786
Category: KMP
Rank: Platinum 5

KMP 알고리즘을 활용하여 푸는 문제입니다.

KMP 알고리즘: https://grujam.github.io/algorithm/KMP/

문제 풀이

이전에 정의해둔 KMP 알고리즘을 사용하여 문제를 해결하였습니다.

주의해야 할 점은 54퍼에서 틀렸습니다가 발생하였는데, 이 문제는 찾게되는 문자열만 getline을 통해 받고 찾아야 하는 문자열은 cin을 통해 받아 발생한 오류였습니다.

두 문자열 모두 getline을 통해 입력받는다면 오류가 해결됩니다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<int> makepi(string str)
{
    int m = str.length();
    int j = 0;

    vector<int> pi(m, 0);

    for(int i = 1; i < m; i++)
    {
        while (j > 0 && str[i] != str[j])
            j = pi[j - 1];
        if (str[i] == str[j])
            pi[i] = ++j;
    }

    return pi;
}

vector<int> KMP(const string& Findee, const string& Finder, const vector<int>& pi)
{
    int j = 0;
    int fdeesize = Findee.size();
    int fdersize = Finder.size();

    vector<int> ret;

    for(int i = 0; i < Findee.length(); i++)
    {
        while (j > 0 && Findee[i] != Finder[j])
            j = pi[j - 1];
        if(Findee[i] == Finder[j])
        {
            if (j == fdersize - 1)
            {
                ret.push_back(i - fdersize + 2);
                j = pi[j];
            }
            else
                ++j;
        }

    }

    return ret;
}

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

    string Finder, Findee;
    getline(cin, Findee);
    getline(cin, Finder);

    vector<int> ans = KMP(Findee, Finder, makepi(Finder));

    cout << ans.size() << '\n';

    for(int& i : ans)
    {
        cout << i << '\n';
    }

    return 0;
}