====== 찾기 ======
  * 문제 제목의 압박.. 너무나도 제너럴한 이름..

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

===== 코드 =====
<dkpr py>
"""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()
</dkpr>

{{tag>BOJ ps:problems:BOJ:골드_1 ps:problems:BOJ:Class_4E}}