백준 1701번: Cubeditor (C++)

접근

https://www.acmicpc.net/problem/1701

1701번: Cubeditor

kmp 알고리즘에 대해서 다시 한 번 공부하여 풀었다. kmp 알고리즘에 대해서는 아래 링크의 글이 가장 자세히 설명된 것 같아 참고차 링크 걸어두었다.

https://bowbowbow.tistory.com/6

KMP : 문자열 검색 알고리즘

kmp 알고리즘에서 접두사 == 접미사 인 문자열의 길이를 구하는 GetPi 함수를 이용하여 문제를 해결할 수 있다. 실제 kmp 알고리즘에서는 이 Pi 배열을 이용하여 문자열이 일치하지 않을 때 건너뛰어 접두사 == 접미사 인 곳부터 다시 탐색하기 위하여 이 함수를 사용하지만, 이 문제에서는 이 접두사 == 접미사 인 경우 해당 길이의 문자열이 접두사에서 1회, 접미사에서 1회 총 2회 사용되었다는 점을 활용하였다.

즉, GetPi 함수를 이용하여 Pi 배열을 완성하고 나면, 이 Pi 배열의 최대값이 바로 Cubeditor 문제에서 요구하는 두번 이상 나오는 문자열 중 최대 길이가 된다. 주어진 문자열에서 나오는 모든 문자열의 Pi 배열을 만드는 것은 어쩔 수 없이 loop을 통해 모두 계산해야 하지만, Pi 배열의 최대값을 통해서 답을 빠르게 구할 수 있다.

코드

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

using namespace std;

#define endl '\n'

string word;

vector<int> GetPi(string p) {
    vector<int> Pi(p.length());
    for (int i = 1, j = 0; i < p.length(); i++) {
        while (j > 0 && p[i] != p[j]) j = Pi[j - 1];
        if (p[i] == p[j]) Pi[i] = ++j;
    }
    return Pi;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> word;

    int Max = 0;
    for (int i = 0; i < word.length(); i++) {
        vector<int> Pi = GetPi(word.substr(i, word.length() - i));
        for (int j = 0; j < word.length() - i; j++) {
            if (Pi[j] > Max) Max = Pi[j];
        }
    }
    cout << Max << endl;

    return 0;
}

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!