[백준] 1701번 Cubeditor

1701 Cubeditor

문제

---

Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.

텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다.  Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.

예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.

이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.

예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.

입력

---

첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.

출력

---

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

---

풀이)

2번 이상 나오는 같은 문자열의 최대 길이를 구하는 문제이다 => prefix와 suffix의 개념을 이용해서 풀자.

Prefix : (=접두사)문자열의 첫번째 문자부터 시작되는 부분문자열,

Suffix : (=접미사)문자열의 마지막 문자부터 거꾸로 보는 부분문자열

예시로 문자열 ALGORITHM이 있다고 하자

prefix = A

AL

ALG

ALGO

.

.

.

ALGORITHM

suffix  = M

HM

THM

ITHM

.

.

.

ALGORITHM

본인 자기자신의 문자열을 제외하면 proper prefix, proper suffix라고 한다.

위의 개념을 이용해 문제에서는

∴ 자기 자신 문자열을 제외하고 & 접두사와 접미사가 완전히 겹치지 않으면서 접두사 == 접미사인 최대 길이의 부분문자열을 찾으면 된다. (접두사와 접미사가 같다는 건, 같은 부분 문자열이 2번 나옴을 보장)

  구하는 과정은 KMP algorithm의 전처리 방법(실패 함수)을 사용했다.

주의사항

접두사의 시작인덱스를 0으로 두고, 한번만 부분문자열을 찾으면 이 문제는 풀지 못한다.

주어진 문자열의 시작 접두사 위치를 변경해줘야한다.

반례(ex) baaa     정답: 2

접두사 시작 위치

baaa => baaa

baaa => aaa

baaa => aa

baaa => a        4번의 확인이 필요

코드)

#include <stdio.h>
#include <iostream>
#include <string>
using namespace std;
 
#define MAX 5001
 
string P;
int F[MAX];
int result;
 
int main() {
    
    cin >> P;
 
    //접두사의 인덱스를 0으로 고정시키면 안됨
    for (int start = 0; start < P.length(); start++) { //접두사 인덱스 변경
        string temp_P = P.substr(start, P.length());
        
        for (int t = 0; t < temp_P.length(); t++) {
            F[t] = 0;
        }
 
        int i = 1;
        int j = 0;
        while (i < temp_P.length())
        {
            if (temp_P[i] == temp_P[j]) {
                F[i] = j + 1;
                i = i + 1;
                j = j + 1;
            }
            else if (j > 0) {
                j = F[j - 1];
            }
            else {
                F[i] = 0;
                i = i + 1;
            }
        }
        for (int i = 0; i < temp_P.length(); i++) {
            if (result < F[i]) {
                result = F[i];
            }
        }
    
    }
    
    printf("%d", result);
    return 0;
}