-
[JAVA] 백준 1701 Cubeditor알고리즘 공부/문제 풀이 2021. 9. 28. 11:34
https://www.acmicpc.net/problem/1701
풀이
n인 어떤 문자열이 주어졌을 때 i = 0 부터 n-1 까지의 경우에 대해 kmp 알고리즘을 적용하고 가장 큰 값을 찾는 문제.
아직까지 kmp 알고리즘이 완벽하게 이해되지 않아서 어려웠다..
[참고]
https://validming99.tistory.com/162
코드
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int answer = 0; for(int i=0; i<str.length(); i++){ String sub = str.substring(i); int max = 0; int pi[] = new int[sub.length()]; //부분 문자열 for(int j=1, k=0; j<sub.length();j++){ //j: 접미사 인덱스, k:접두사 인덱스 while(k>0 && sub.charAt(j) != sub.charAt(k)) k = pi[k-1]; if(sub.charAt(j) == sub.charAt(k)) max = Math.max(max, pi[j] = ++k); } answer = Math.max(answer, max); } System.out.println(answer); } }
'알고리즘 공부 > 문제 풀이' 카테고리의 다른 글
[JAVA] 백준 1194 달이 차오른다, 가자 (0) 2021.09.29 [JAVA] SWEA Professional 구간 합 (0) 2021.09.28 [JAVA] 백준 1707 이분 그래프 (0) 2021.09.28 [JAVA] 백준 9660 돌 게임 6 (0) 2021.09.27 [JAVA] 백준 15993 1, 2, 3 더하기 8 (0) 2021.09.27