[1. 문제 설명]
https://www.acmicpc.net/problem/1786
[2. 풀이 접근]
KMP 알고리즘 (Text 에서 Pattern 이 존재하는 모든 시작위치를 반환)
- T[i...] 에서 P[...n] 이 일치하지만, P[n+1] 에서 불일치 한 경우
- 다음 탐색 위치를 좀 더 효율적으로 설정하여 탐색 속도를 빠르게 한다.
- P[...n] 이 일치하였으므로, P[...n] 에서 접두사와 접미사가 같은 곳이 있다면,
- 탐색 위치를 접두사 길이 만큼 점프할 수 있다.
[3. 코드]
'알고리즘 > Baekjoon' 카테고리의 다른 글
| 구간 트리. [10868] (0) | 2022.12.22 |
|---|---|
| 우선 순위 큐. [1715] (0) | 2022.12.22 |
| BFS. [14502] (0) | 2022.12.20 |
| 이진트리. [9934] (0) | 2022.12.15 |
| 트리. [1086] (0) | 2022.12.14 |