[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://github.com/fpdjsns/Algorithm/blob/master/BOJ/11585.%20%EC%86%8D%ED%83%80%EB%8A%94%20%EC%A0%80%EB%85%81%20%EB%A9%94%EB%89%B4.cpp

---

알고리즘 머리에 저장하려고 KMP 도장깨기 중. 반복만이 살길이다.