사용자 도구

사이트 도구


ps:problems:boj:13576

Prefix와 Suffix

ps
링크acmicpc.net/…
출처BOJ
문제 번호13576
문제명Prefix와 Suffix
레벨플래티넘 2
분류

문자열

시간복잡도O(n)
인풋사이즈n<=100,000
사용한 언어Python 3.11
제출기록48604KB / 240ms
최고기록240ms
해결날짜2022/12/17

풀이

  • 모든 border에 대해서 등장 횟수를 구하라는 문제이다.
  • 모든 prefix의 등장 횟수 세기는 O(n)에 가능하고, 모든 Border 찾기도 O(n)에 가능하다. 실패함수를 써서 하는 방법과 z 배열을 써서 하는 방법 모두 링크에 설명되어있다.
  • 두가지를 조합하기만 하면 된다. 모든 prefix의 등장횟수를 구해놓은 뒤에, border들에 대해서만 그 값을 출력하면 끝.
  • kmp와 z algorithm 두가지를 다 구해봤는데, 속도는 거의 비슷했다. 코드는 z algorithm쪽이 살짝 간단하긴 한데 대동소이..

코드

코드 1 - fail 함수 이용

"""Solution code for "BOJ 13576. Prefix와 Suffix".

- Problem link: https://www.acmicpc.net/problem/13576
- Solution link: http://www.teferi.net/ps/problems/boj/13576

Tags: [KMP]
"""

import collections
from teflib import string as tstring


def main():
    S = input()
    fail = tstring.failure_table(S)

    counter = collections.Counter(fail)
    for i in range(len(S) - 1, 0, -1):
        counter[fail[i - 1]] += counter[i]
        counter[i] += 1
    counter[len(S)] = 1

    l = len(S)
    border_lens = [len(S)]
    while l := fail[l - 1]:
        border_lens.append(l)

    print(len(border_lens))
    for x in reversed(border_lens):
        print(x, counter[x])


if __name__ == '__main__':
    main()

코드 2 - z 배열 이용

"""Solution code for "BOJ 13576. Prefix와 Suffix".

- Problem link: https://www.acmicpc.net/problem/13576
- Solution link: http://www.teferi.net/ps/problems/boj/13576

Tags: [Z algorithm]
"""

import collections
from teflib import string as tstring


def main():
    S = input()
    z = tstring.z_array(S)

    counter = collections.Counter(z)
    for i in reversed(range(len(S))):
        counter[i] += counter[i + 1]
    border_lens = [i for i, z_i in enumerate(reversed(z), start=1) if i == z_i]

    print(len(border_lens))
    for x in border_lens:
        print(x, counter[x])


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
S S E​ D G
 
ps/problems/boj/13576.txt · 마지막으로 수정됨: 2022/12/17 03:23 저자 teferi