알고리즘

개념

문자열과 패턴을 해시화 시켜서 (아스키 코드 값으로) 비교한다.

해시 값이 같으면 그 때 문자열을 직접비교 한다.

이게 빠른 이유는 $2^i$ 꼴로 해시를 하기 때문에 한번 오른쪽으로 이동하면 가장 앞의 $2^i$ 자리의 문자를 빼주고 2를 곱한 후 새로운 문자를 더하는 방식으로 문자를 다시 앞에서 볼 필요가 없기 때문이다.

라빈 핑거프린트

시간복잡도

O(N) 처음부터 끝까지 해시값을 구해나가면 됨

작동과정 / 예시코드

import sys
input=sys.stdin.readline

MOD=1000000000000007
def mod(n):
    if n>=0: return n%MOD
    else: return ((-n//MOD+1)*MOD+n)%MOD
    
if __name__=="__main__":
    t=input().rstrip()
    p=input().rstrip()
    n,m=len(t),len(p)
    
    res=[]
    g,h=0,0
    power=1
    for i in range(n-m+1):
        if i==0: #가장 처음 해시값을 계산
            for j in range(m):
                g=mod(g+ord(t[m-1-j])*power)
                h=mod(h+ord(p[m-1-j])*power)
                if j<m-1: power=mod(power*7)  #가장 큰 값으로 그대로 유지 (이 부분을 빼줘야 하니까)
        else: g = mod(7*(g-ord(t[i-1])*power) + ord(t[i+m-1]))
        if g==h:
            res.append(i+1)
    print(len(res))
    print(*res)