백준 1786 : 찾기 (C++)

본문 링크

#include <iostream>
#include <vector>

using namespace std;
vector<int> answer;

vector<int> maketable(string pattern) // 실패함수.
{

    int patternsize = pattern.size();

    vector<int> table(patternsize , 0);

    int j = 0;

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

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

    return table;
}

void KMP(string pattern , string parent)
{
    vector<int> table=maketable(pattern);

    int patternsize=pattern.size();
    int parentsize=parent.size();

    int j=0;

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

        if (parent[i]==pattern[j])
        {
            if (j==patternsize-1)
            {
                answer.push_back(i-patternsize+2);
                j=table[j];
            }
            else
            {
                j++;
            }
        }
    }
}

int main()
{
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    string parent , pattern;

    getline(cin , parent);
    getline(cin , pattern);

    KMP(pattern , parent);

    cout << answer.size() << "\n";

    for (int i = 0 ; i < answer.size() ; i++)
    {
        cout << answer[i] << " ";
    }

    return 0;   
}

📌 어떻게 접근할 것인가?

KMP 기초 문제입니다.

getline 을 통해 공백을 포함하여 한줄을 입력받습니다.

이후 maketable 이라는 실패함수를 만들어 주고 KMP 함수에서 실패 함수를 활용하여 $O(N+M)$ 의 시간복잡도로 두 문자열을 비교해주었습니다.

KMP 에 대한 자세한 내용은 나동빈 - KMP 강의 의 사이트를 통해 공부하였습니다.