ps:problems:boj:13713
문자열과 쿼리
| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 13713 |
| 문제명 | 문자열과 쿼리 |
| 레벨 | 플래티넘 5 |
| 분류 |
문자열 |
| 시간복잡도 | O(n+m) |
| 인풋사이즈 | n<=1,000,000, m<=100,000 |
| 사용한 언어 | Python 3.11 |
| 제출기록 | 79964KB / 840ms |
| 최고기록 | 796ms |
| 해결날짜 | 2022/12/15 |
풀이
- F(i)의 정의를 살펴보면, 결국 S를 뒤집어서 만든 문자열 S[::-1]에 대해 z배열을 만든것과 동일하다.
- z배열을 O(n)에 구하면 모든 쿼리를 O(1)에 대답 가능하다.
코드
"""Solution code for "BOJ 13713. 문자열과 쿼리".
- Problem link: https://www.acmicpc.net/problem/13713
- Solution link: http://www.teferi.net/ps/problems/boj/13713
Tags: [Z algorithm]
"""
import sys
from teflib import string as tstring
def main():
S = sys.stdin.readline().rstrip()
z_arr = tstring.z_array(S[::-1])
M = int(sys.stdin.readline())
for _ in range(M):
i = int(sys.stdin.readline())
print(z_arr[-i])
if __name__ == '__main__':
main()- Dependency: teflib.string:z-array
ps/problems/boj/13713.txt · 마지막으로 수정됨: 2022/12/16 08:28 저자 teferi
토론