사용자 도구

사이트 도구


ps:problems:boj:1786

찾기

ps
링크acmicpc.net/…
출처BOJ
문제 번호1786
문제명찾기
레벨골드 1
분류

문자열 매칭

시간복잡도O(n+m)
인풋사이즈n<=10^6, m<=10^6
사용한 언어Python
제출기록56544KB / 752ms
최고기록548ms
해결날짜2020/12/26
  • 문제 제목의 압박.. 너무나도 제너럴한 이름..

풀이

  • 기본적인 문자열 매칭 문제
  • O(n+m) 매칭 알고리즘을 사용하면, KMP나 (해시를 잘 준)라빈카프 어느쪽으로도 풀 수 있다. 여기서는 라빈카프로 해결.
    • 제출시간 상위 코드들은 다 KMP이긴 하다.

코드

"""Solution code for "BOJ 1786. 찾기".

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


from typing import Generator


_RADIX = 256


def fingerprint(text: str, mod: int = 1_000_000_007) -> int:
    """Returns Rabin fingerprint of given text."""
    h = 0
    for ch in text:
        h = (_RADIX * h + ord(ch)) % mod
    return h


def gen_fingerprints(
    text: str, length: int, mod: int = 1_000_000_007
) -> Generator[int, None, None]:
    """Yields Rabin fingerprints of all k-length substrings of given text."""
    h = fingerprint(text[:length])
    yield h
    p = pow(_RADIX, length - 1, mod)
    for drop, add in zip(text, text[length:]):
        h = (h - (ord(drop) * p)) % mod
        if h < 0:
            h += mod
        h = (_RADIX * h + ord(add)) % mod
        yield h


def main():
    T = input()
    P = input()

    p_hash = fingerprint(P)
    posititons = [pos + 1
                  for pos, t_hash in enumerate(gen_fingerprints(T, len(P)))
                  if t_hash == p_hash]
    print(len(posititons))
    print(*posititons)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
I Q᠎ X I D
 
ps/problems/boj/1786.txt · 마지막으로 수정됨: 2020/12/26 16:11 저자 teferi