ps:problems:boj:4354
문자열 제곱
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 4354 |
| 문제명 | 문자열 제곱 |
| 레벨 | 플래티넘 5 |
| 분류 |
문자열 |
| 시간복잡도 | O(t*n) |
| 인풋사이즈 | t<=?, n<=1,000,000 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 36308KB / 168ms |
| 최고기록 | 168ms |
| 해결날짜 | 2022/12/16 |
풀이
- 문자열의 반복 패턴을 찾자.
- 링크에서 설명했듯이, S를 A^n 형태로 표현할 수 있는지 여부와 그때의 가장 짧은 A의 길이는, fail함수를 이용해서 구할수도 있지만, 그냥 builtin str.find 함수를 사용해서 훨씬 빠르게 구할수 있다. 시간복잡도는 kmp와 같은 O(n)이지만, kmp를 구현해서 풀었을때에는 2000ms이상 걸리던 것이 str.find를 이용하면 200ms 이내에 풀린다.
코드
"""Solution code for "BOJ 4354. 문자열 제곱".
- Problem link: https://www.acmicpc.net/problem/4354
- Solution link: http://www.teferi.net/ps/problems/boj/4354
"""
def main():
while (s := input()) != '.':
print(len(s) // (s + s).find(s, 1))
if __name__ == '__main__':
main()ps/problems/boj/4354.txt · 마지막으로 수정됨: 2022/12/16 14:40 저자 teferi
토론