[1. 문제 설명]
https://www.acmicpc.net/problem/11585
[2. 풀이 접근]
kmp search
- 원형에 대해서 문자열을 이어 붙이고,
- 이 문자열에서 다른 문자열을 찾는 전형적인 kmp 탐색 문제이다.
주의 할 점
- 주석에도 언급했지만, 이어붙인 문자열 X=2B 에 대해서
- X[len(B)...] 에서 A 를 찾는 것은 의미가 없다.
기약 분수
- 분자와 분모의 최대공약수를 찾아야 한다.
- 유클리드 호제법을 이용하여 계산하도록 한다.
- 생각이 안나서 과거에 정리한 글을 참조
- https://testkernelv2.tistory.com/107
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| kmp. [13506] (0) | 2023.05.02 |
|---|---|
| kmp. [7575] (0) | 2023.04.27 |
| kmp. [10266] (0) | 2023.04.24 |
| kmp. [4354] (0) | 2023.04.21 |
| kmp. [1701] (0) | 2023.04.21 |