백준 16916

부분 문자열

처음으로 풀어보는 문자열 문제.
이 문제를 풀기 위해 내가 사용한 알고리즘은 라빈 카프 알고리즘이다.
라빈 카프 알고리즘을 내가 이해한 바대로 간단히 설명하면,
해시 함수를 이용해서 각각의 ascii code 값을 더하여 비교하는 알고리즘이다.
다음 줄부터 라빈 카프 알고리즘을 자세히 설명하겠다.

라빈 카프 알고리즘

1. 각 글자마다 ascii code값을 더하고 비교하기 때문에 브루트포스 알고리즘과 다를 바가 없이 여전히 시간복잡도는 O(S*P)가 된다.

   그렇다면? 각 부분의 hash값의 맨 앞 ascii값을 빼고 부분 문자열+1번째 ascii값을 더해준다.

2. 위처럼 하면 hash(“abc”)==hash(“cba”)가 된다.

   그렇다면? 각 문자열의 각 index에 특정 수를 곱해준다. 3자리 문자열이라고 가정하면 3번 밑의 표와 같다.

3. 위처럼 하면 hash(‘aaaaa’)는 무척 큰 값이 된다.

   적당한 소수값을 정해 mod시켜준다.

	a[0]	a[1]	a[2]
a[i]	a[0]*256^2	a[1]*256^1	a[2]*256^0

위와 같이 라빈 카프 알고리즘의 아이디어를 정리할 수 있다.
밑은 위의 아이디어를 문제에 맞추어 코드화한 것이다.
오타나 질문, 잘못된 점 모두 댓글로 남겨주시면 감사하겠습니다.

소스

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int h(string s) {
	int ans=0;
	for (auto ch:s) {
		ans = (ans * 256 + ch) % 127;
	}
	return ans;
}
int main() {
	string p;
	string s;
	cin >> s >> p;
	int n = s.size();
	int m = p.size();
	if (n < m)
	{
		cout << "0\n";
		return 0;
	}
	int hash_p=h(p);
	int hash_s=h(s.substr(0,m));
	int first = 1;
	for (int i = 0; i < m - 1; i++)
	{
		first = (first * 256) % 127;
	}
	for (int i = 0; i <= n-m; i++)
	{
		if (hash_p == hash_s)
		{
			if (s.substr(i, m) == p) {
				cout << "1\n";
				return 0;
			}
		}
		if ((i + m )< n)
		{
			hash_s = hash_s - (s[i] * first) % 127;
			hash_s = (hash_s + 127) % 127;
			hash_s = ((hash_s * 256) % 127 + s[i + m]) % 127;
		}
		
	}
	cout << "0\n";
}