Algospot NAMING

문제 링크입니다: https://algospot.com/judge/problem/read/NAMING

많은 사람들이 기피하는 문자열 알고리즘 KMP 알고리즘 문제였습니다.

KMP 알고리즘의 자세한 설명은 종만북도 좋지만 http://blog.naver.com/kks227/220917078260에서도 상세하게 설명해주시기 때문에 참고하는 것을 추천합니다.

브루트 포스 기법을 통해 문자열을 찾을 경우 시간복잡도가 O(N*M)이지만, KMP 알고리즘을 사용할 경우 시간복잡도가 O(N+M)으로 향상되기 때문에 어렵더라도 많이 보면서 코드를 익히는 것이 좋을 것 같습니다!

(문자열의 길이:M, 부분문자열의 길이: N)

#include <iostream>

#include <vector>

#include <string>

using namespace std;

 

//N에서 자기 자신을 찾으면서 나타나는 부분일치를 이용해 pi[]를 계산

//pi[i] = N[,,i]의 접미사도 되고 접두사도 되는 문자열의 최대 길이

vector<int> getPartialMatch(const string &N)

{

        int m = N.size();

        vector<int> pi(m, 0);

        //KMP로 자기 자신을 찾는다

        //N을 N에서 찾는다. begin=0이면 자기 자신을 찾아버리니까 안됨

        int begin = 1, matched = 0;

        //비교할 문자가 N의 끝에 도달할 때까지 찾으면서 부분일치 모두 기록

        while (begin + matched < m)

        {

                 //begin+matched에 있는 문자와 matched에 있는 문자 일치

                 if (N[begin + matched] == N[matched])

                 {

                         ++matched;

                         pi[begin + matched - 1] = matched;

                 }

                 //일치하지 않고

                 else

                 {

                         //matched가 0인 경우 begin을 한칸 앞으로

                         if (matched == 0)

                                 ++begin;

                         //matched가 0이 아니면

                         else

                         {

                                 //begin을 (matched - 일치하는 접미사/접두사의 길이)만큼 더한다

                                 begin += matched - pi[matched - 1];

                                 matched = pi[matched - 1];

                         }

                 }

        }

        return pi;

}

 

//s의 접두사도 되고 접미사도 되는 문자열들의 길이 반환

vector<int> getPrefixSuffix(const string &s)

{

        vector<int> result, pi = getPartialMatch(s);

        int k = s.size();

 

        while (k > 0)

        {

                 //s[..k-1]는 답

                 result.push_back(k);

                 //s[,,k-1]의 접미사도 되고 접두사도 되는 문자열도 답이다

                 k = pi[k - 1];

        }

        return result;

}

 

int main(void)

{

        string father, mother;

        cin >> father >> mother;

 

        string combined = father + mother;

 

        vector<int> result = getPrefixSuffix(combined);

 

        //오름차순으로 출력하려면 역순으로 출력해야한다

        for (int i = result.size()-1; i>=0; i--)

                 cout << result[i] << " ";

        cout << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략