문제 링크
- http://icpc.me/13506
사용 알고리즘
- KMP
시간복잡도
- O(N)
풀이
S의 Prefix이면서 동시에 Suffix인 것들의 길이는 fail(N),fail(fail(N)),fail(fail(fail(N))),⋯ 뿐입니다.
Failure Function의 구축 과정을 잘 생각해보면, fail(N)을 제외한 fail(fail(N)),fail(fail(fail(N))),⋯은 중간에 한 번 이상 더 나온다는 사실을 알 수 있습니다.
Failure Function을 구한 뒤, Failure Function을 쭉 따라가면서 정답을 구하면 됩니다.
전체 코드
1 |
|