백준 1701 : Cubeditor (C++)

본문 링크

#include <iostream>
#include <vector>
#include <algorithm>


using namespace std;

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[j]==pattern[i])
        {
            table[i]=++j;
        }
    }

    return *max_element(table.begin(), table.end());
}

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

    string pattern;
    
    getline(cin , pattern);


    int total=0;

    for (int i = 0 ; i < pattern.size() ; i++)
    {
        total = max(total , maketable(pattern.substr(i,pattern.size())));
    }
    cout << total ;
}

/*
주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.

실패함수에서 값의 뜻은 접미사와 접두사가 같다는 것. 
즉 실패함수로 만든 table 값이 0 보다 크다면 접두사와 접미사가 같다는 것이므로
부분문자열이 2번 등장했다는 의미이다.

따라서 table 값중 가장 큰 값을 출력한다.
*/

📌 어떻게 접근할 것인가?

KMP 응용 문제입니다. 실패함수를 응용해야합니다.

문제에서 원하는 것은 두번 이상 나오는 부분문자열의 최대 길이입니다.

실패함수란 , 접두사와 접미사가 같은 최대 길이를 저장하는 함수입니다.

즉 실패함수에 aba 라는 값이 있다면 0 0 1 이 나올것이고 1 이라는 값은 이전에 문자열에 a 라는 똑같은 문자가 나왔다는 뜻입니다.

즉 실패함수에 있는 배열의 값은 접두사와 접미사의 중복문자이기 때문에 두 번 이상나왔다고 말할수 있으며

따라서 실패함수의 최대값이란 두번이상 나오는 부분문자열의 최대값을 의미합니다.

실패함수 maketable 을 만들어 주고 *max_element(table.begin(), table.end()); 를 반환했습니다.

이때 #inclued <algorithm> 을 사용해야합니다.