KMP2 [BOJ][11585] 속타는 저녁 메뉴 문제 : https://www.acmicpc.net/problem/11585 두번째 문장을 2개 이어붙인 문자열에서 세번째 문장이 몇 번 나오는지 찾는다. 이를 KMP로 찾을 수 있다. 주의할 점은 입력값이 ABCDE, ABCDE인 경우 정답은 1/5 이지만 2/5 가 출력된다. 두번째 문장을 2개 이어붙였기 때문에 ABCDEABCDE에서 실제로는 1개지만 빨, 파 2 번 나타났다고 판단했기 때문이다. 따라서 패턴문자열을 찾았을 때 첫번째 문자열을 시작으로 하는 부분문자열에서 패턴이 나타났다면 1을 빼준다. KMP로 구한 패턴문자열이 나타낸 횟수가 분자, 문자열 길이(N)가 분모가 된다. 기약분수는 최대공약수를 유클리드로 구해서 분자, 분모에 나눠주면 된다. 시간복잡도는 O(N). 소스코드 : https.. 2020. 4. 8. KMP 알고리즘 만든 사람이 Knuth, Morris, Pratt 여서 Knuth–Morris–Pratt(KMP) 알고리즘이라 합니다. 문자열 알고리즘 중 하나로 문자열 에서 다른 문자열을 검색하는 알고리즘입니다. 단순하게 문자열(S) "ABCABDABCABC" 에서 문자열(P) "ABCABC"를 검색해봅시다. S, P 모두 가장 앞에서부터 같은지 비교합니다. (1) ~ (5) 는 문자가 같기 때문에 다음 문자를 비교합니다. (6) D, C는 다르기 때문에 문자열 P를 찾을 수 없습니다. 이제 S 문자열의 인덱스 1부터 다시 비교합니다. (1) B, A는 다르기 때문에 문자열 P를 찾을 수 없습니다. 문자열 P를 찾을 때까지 이를 반복합니다. 문자열 S 인덱스 6부터 시작하는 부분문자열에서 문자열 P를 찾을 수 있었습니.. 2020. 2. 9. 이전 1 다음
