[백준 / BOJ] 1701 Cubeditor

문제

출처 : www.acmicpc.net/problem/1701

1701번: Cubeditor

Cubelover는 텍스트 에디터 Cubeditor를 만들었다. 이 에디터가 다른 에디터와 다른점은, 찾을려하는 문자열이 2번이상 존재해야지 찾는것이다.

예를들어, ababac에서 aba를 찾을려하면 ababac 이렇게 찾을수있다. c를 찾을려하면 c는 한번밖에 나오지 못하므로 찾지못한다.

 

풀이

완전탐색으로 풀려할경우, 약 5000^3 반복할수있어서 시간초과가 난다.

KMP알고리즘을 약간 변형해 풀어야하는 문제였다.

 

가장 긴 중복 부분문자열을 찾아야한다.

KMP알고리즘의 희소배열을 만들면 접두사와 접미사가같은 최장 문자열을 찾을수있다.

문제는, 문자열에서 희소배열을 만들때, 비교할려는 배열의 0번 인덱스를 기준으로 접미사를 찾는다는건데, 중복 부분문자열이 0번부터 시작하지않을수있다. 따라서,

0~str.size()까지 반복하며, 가장긴 중복 부분문자열을 찾으면된다.

예를들어,

1. 시작값 : 0일때, 0번 인덱스부터 str.size()-1까지 중복문자열을 찾는다.

2. 시작값 : 1일때, 1번인덱스부터 str.size()-1까지 중복문자열을 찾는다.

3. 시작값 : 2일때, 2번인덱스부터 str.size()-1까지 중복문자열을 찾는다.

.

.

.

이렇게 반복해주면되는데, 주의할점이 비교해줄 문자열과, 비교할 문자열 둘다 시작값지점부터 비교해줘야한다는것이다.

 

시간복잡도는,

한번반복하는데, str.size() - 시작값이고, 시작값이 str.size()까지 갈수있으므로, 

(str.size()+1)*(str.size()/2) 가 된다.

소스코드

https://github.com/devxb/JJUNalgo/blob/master/1701%20cubeditor/main.cpp

devxb/JJUNalgo