라빈 카프, 문자열 해싱

어떤 문자열의 부분 문자열을 해싱하려 할때, map을 이용하여 mp[s.substr(i,k)]꼴로 해시를 사용하기엔 이미 substr이 선형시간을 잡아먹으므로 바람직하지 않다.

 

문자열 s에 대해 해시함수를 다음과 같이 쓰는 걸 라빈카프라 한다.

출처: https://blog.encrypted.gg/857

(혼동을피하기위해 a->p  p->MOD)

큰 소수 MOD의 원시근으로 p를 고르는 것이 유리하다.

 

문자열 s의 i번째부터 시작하는 길이k인 부분문자열을 위 식에 넣어 정리해보면 다음과 같이 점화식이 나온다.

H[i+1] = p*H[i] - (p^k)*s[i] + s[i+k]

for (int i = 1; i <= n - k; i++) {
	h = mod(p*h - pow_p[k]*s[i-1] + s[i+k-1]);
}

 

---

https://www.acmicpc.net/problem/1786

문자열 S에서 패턴T가 어디서 매칭되는지 모두 출력하는 문제. 길이 <= 1e6

 

패턴 t의 해시값 target과

문자열 s의 길이가 t.size()인 부분수열들의 해시값을 비교해서 해시값이 같은 인덱스를 출력하면 된다.

 

<코드>

const int MAX = 1e6 + 4;
const ll p = 302;
const ll MOD = 1e9 + 7;

ll n, m, pow_p[MAX];
string s, t;
void init() {
	n = s.size();
	m = t.size();
	pow_p[0] = 1;
	for (int i = 1; i < MAX; i++)
		pow_p[i] = (pow_p[i - 1] * p) % MOD;
}
ll mod(ll x) {
	if (x >= 0) return x % MOD;
	return (x + ((-x) / MOD + 1) * MOD) % MOD;
}

int main() {
	FAST;
	getline(cin, s);
	getline(cin, t);
	init();

	if (n < m) {
		cout << 0;
		return 0;
	}

	ll h = 0, target = 0;
	for (int i = 0; i < m; i++) {
		h = mod(h + s[i] * pow_p[m - 1 - i]);
		target = mod(target + t[i] * pow_p[m - 1 - i]);
	}

	vector<int> ans;
	if (h == target) ans.push_back(1);
	for (int i = 1; i <= n-m; i++) {
		h = mod(p * h - pow_p[m] * s[i - 1] + s[i + m - 1]);
		if (h == target) ans.push_back(i + 1);
	}
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << " ";
}

 

<생각>

MOD를 충분히 크게하고 적절한 p를 고른다면 99.990%의 확률로 통과한다.

-> 반례 케이스가 있는 문제들이 많으므로 막 쓰면 안된다. 그냥 문자열 해싱하는거 연습용