사용자 도구

사이트 도구


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()

토론

댓글을 입력하세요:
H G W A N
 
ps/problems/boj/13713.txt · 마지막으로 수정됨: 2022/12/16 08:28 저자 teferi