Prefix와 Suffix

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

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

• Dependency: teflib.string.failure_table

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

• Dependency: teflib.string.z_array