KMP2 [알고리즘] 찾기 KMP (백준 1786번) 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 정확하게 KMP를 구현하는 문제다. 패턴 매칭 실패 시 패턴 인덱스 j 가 돌아갈 곳을 지정하는 failureFunction을 구하는 메서드와 그걸 이용해서 패턴 매칭을 하는 KMP 메서드로 이루어져있다. 주로 겹쳐져있는 패턴도 찾아낼 때에 사용한다. EX) 텍스트 : ababa, 패턴 : aba → 패턴 개수 : 2개 String.replace로는 찾아낼 수 없는 경우임 import java.io.BufferedReader; import java.io.. 2020. 8. 27. [알고리즘] 문자열 폭발 (백준 9935번) 9935번: 문자열 폭발 문제 상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다. 폭발은 다음과 같은 과정으로 진행된다. 문자열이 www.acmicpc.net 폭발 문자열, 즉 특정 패턴을 찾아서 매칭되면 그 패턴에 해당하는 문자열을 삭제하고, 새로 만들어진 문자열에서 또 패턴을 찾아 삭제하라는 문제이다. 당연하겠지만 String.replaceAll로 반복문을 돌리는 것은 메모리 초과, 혹은 시간 초과로 불가능하다. O(N) 만큼의 시간복잡도로 패턴을 찾아 파괴하는 것이 포인트이다. 1. failureFunction 만들기 KMP를 응용하여 failureFunction을 만들어서 비교 문자가 같지 않은 경우 pattern 인.. 2020. 8. 26. 이전 1 다음
