[백준]#1701 Cubeditor
문제
Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다.
텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에디터는 찾으려고 하는 문자열이 단 한 번만 나와도 찾는다. Cubelover는 이 기능은 Cubelang에 부적합하다고 생각했다. Cubelang에서 필요한 기능은 어떤 문자열 내에서 부분 문자열이 두 번 이상 나오는 문자열을 찾는 기능이다. 이때, 두 부분 문자열은 겹쳐도 된다.
예를 들어, abcdabc에서 abc는 두 번 나오기 때문에 검색이 가능하지만, abcd는 한 번 나오기 때문에 검색이 되지를 않는다.
이렇게 어떤 문자열에서 두 번 이상 나오는 부분 문자열은 매우 많을 수도 있다. 이러한 부분 문자열 중에서 가장 길이가 긴 것을 구하는 프로그램을 작성하시오.
예를 들어, abcabcabc에서 abc는 세 번 나오기 때문에 검색할 수 있다. 또, abcabc도 두 번 나오기 때문에 검색할 수 있다. 하지만, abcabca는 한 번 나오기 때문에 검색할 수 없다. 따라서, 두 번 이상 나오는 부분 문자열 중에서 가장 긴 것은 abcabc이기 때문에, 이 문자열이 답이 된다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 최대 5,000이고, 문자열은 모두 소문자로만 이루어져 있다.
출력
입력에서 주어진 문자열의 두 번이상 나오는 부분문자열 중에서 가장 긴 길이를 출력한다.
예제 입력 1
abcdabcabb
예제 출력 1
3
풀이
이 문제는 KMP 알고리즘을 알고있다면 풀 수 있는 문제였다. KMP알고리즘을 구현할 때 사용된 이론을 통해서 답을 구할 수 있다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
int max = -1;
for(int i=0; i<input.length(); i++) {
int[] pi = getPi(input.substring(i)); //접두사를 바꿔가며 경우의 수 생각
for(int j=0; j<pi.length; j++)
max = Math.max(max, pi[j]);
}
System.out.println(max);
}
public static int[] getPi(String str) {
char[] pattern = str.toCharArray();
int[] pi = new int[str.length()];
int j = 0;
for(int i=1; i<pattern.length; i++) {
while(j>0 && pattern[i]!=pattern[j]) {
j = pi[j-1];
}
if(pattern[i]==pattern[j]) {
pi[i] = ++j;
}
}
return pi;
}
}
Author And Source
이 문제에 관하여([백준]#1701 Cubeditor), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pss407/백준1701-Cubeditor저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)