[알고리즘 개념정리] 2. 문자열 (Polynomial Rolling hash)+기초지식

**본 포스팅은 22Winter 신촌캠프 초급반 강사 raararaara님의 강의를 참고하여 작성하였습니다.**

 

긴 문자열 S[1...n]내에 패턴 P[1...m]이
부분 문자열로 등장 하는지 알아보자.

S의 부분 문자열 중
길이가 m인 것의 개수는 n-m+1이다.
이를 각각 m글자씩 하나하나 확인하는 방법은
O(nm)에 가깝다.

Polynomial Rolling hash 방법을 사용하면
O(n)에 해결할 수 있다.

Polynomial Rolling hash

시간복잡도 : O(n)
방법 : 문자열을 정수로 치환하여 정수끼리 비교한다.

p(X) = { p[0]*(X^m-1) + p[1]*(X^m-2) + ... + p[m-1]*(X^0) } mod M

// p(x) 는 P[1...m]을 정수화 시킨 값

Sk(X) = { S[k]*(X^m-1) + S[k+1]*(X^m-2) + ... + S[k+m-1]*(X^0) } mod M

// Sk(X) 는 S[1...n]의 부분문자열 S[k...k+m-1]을 정수화 시킨 값

문자열에 영어 소문자(또는 대문자)만 들어가는 경우
'a'=1. 'b'=2, ... 'z'=26 그리고 X=27을 사용한다.
mod는 사용하지 않는다.
(M이 큰 수 일수록 좋은데
애초에 int말고 long long을 사용하면
M을 long long MAX로 설정한 것이나 마찬가지이기 때문이다.)

X값 설정 관련. (출처: 22W 신촌캠프 초급반 슬랙)

 

 

 

---

이제 S0(X)를 구해보자.
m=4라고 하면,
S0(X) = S[0]*X^3 + S[1]*X^2 + S[2]*X^1 + S[3]*X^0 이다.
이를 코드로 구현하면 다음과 같다.

... 
ll num=0; // S0(X) 
ll POW = 1; 
for(int i=m-1; i>=0; i--){ 
	num += (s[i]-'a'+1) * POW; 
	POW *= X; 
} 
...

그 다음, S1(X)를 구할 때는
S0(X)를 이용해 O(1)만에 구할 수 있다.
S1(X) = (S0(X) - S[0]*X^3)X + S[4]*X^0
        = S[1]*X^3 + S[2]*X^2 + S[3]*X^1 +S[4]*X^0




p.s
이 방법으로 문자열 해싱을 하다가
해시 충돌(두 문자열의 내용이 다르지만 해시값이 같은 경우)이 일어난다면
다중 해시를 사용(위의 예에서는 X를 여러 값으로 해보는 것)하여
여러번 체크해보면 된다.

(출처: 22W 신촌캠프 초급반 슬랙)

관련 문제

2022.01.16 - [PS/Baekjoon] - [백준/C++] 5525번: IOIOI(S2)

2022.01.17 - [PS/Baekjoon] - [백준/C++] 2866번: 문자열 잘라내기(G5)

2022.01.17 - [PS/Baekjoon] - [백준/C++] 16916번: 부분 문자열(G3)

2022.01.18 - [PS/Baekjoon] - [백준/C++] 10840번: 구간 성분(G1)

2022.01.24 - [PS/Baekjoon] - [백준/C++] 5052번: 전화번호 목록(G4)

1701. Cubeditor (정답코드) +이분탐색


참고자료 :
https://joooahn.tistory.com/19
https://withhamit.tistory.com/401

 

---

+ 문자열 관련 기초지식 정리☆

1. 부분 문자열 vs 부분 수열
   Substring(부분 문자열) : S의 i번 글자부터 j번 글자까지 연속적으로 구성된 문자열(i<j)
   Subsequence(부분 수열) : 문자열의 일부 글자(연속X여도 됨)가 원래의 순서를 유지하며 나열된 형태
   
   
2. 접두사 vs 접미사
   Prefix(접두사) : S의 0번 글자부터 a번 글자까지로 구성된 부분 문자열 (a < |S|)
   Suffix(접미사) : S의 a번 글자부터 끝까지로 구성된 부분 문자열
   
   
3. 입력방법
   기본 입력(공백 이전까지)
   

   ...
   string S;
   cin >> S;
   ...

   
   공백 포함
   

   ...
   int tc; cin>>tc;
   cin.ignore(); // 구분 문자(delimeter)를 포함하여, 그 이전까지의 문자들을 stream에서 제거
   
   string S;
   getline(cin, S);
   ...​