백준 - 16916 부분 문자열

문제

문자열 s, p가 주어질 때 p가 s의 부분 문자열인지 아닌지 알아내라!

생각

python의 p in s 를 써서 있는지 없는지 알아내려고 했는데
길이가 100만이여서 이게 안 되나보다
별별 방법으로 막 찾고 해봤는데 다 안 된대! ㅜ

근데 이런 부분 문자열을 찾는 O(n)의 시간 복잡도인 유명한 알고리즘 2개가 있댄다
KMP랑 라빈 카프 알고리즘 인 것 같은데,

KMP는 복잡하고 그래서 라빈 카프 알고리즘으로 풀어보려고 한다

라빈 카프 알고리즘

p와 s의 부분 문자열의 해시값을 얻어내서 해시값이 같을 때,
정말 다 같은 문자열인지 확인해주는 방법이다

p의 길이만큼 s를 잘라보면서 해시값을 얻어내주는거랄까..

사실 비교 할 때마다 해시 코드 얻어내고 비교하는 작업은 시간복잡도가 O(s * p)임
O(n)이 되려면 어떻게 해야할까~?

슬라이딩 윈도우로 쭈욱 보면서
맨 왼쪽 해시 값을 빼고, 맨 오른쪽 해시 값을 추가해주면서 서칭을 하게 된다~~
약간 투 포인터 느낌으로 추추추추 지나가서 O(n)만에 비교를 할 수 있는거지!!

그래서 구현 방법은 아래와 같다

해시 함수
각 글자의 아스키 값에 2^base를 곱해주고, 글자들의 합을 해시 코드로 사용!
너무 값이 커질 수 있으니 mod 연산을 해준다

슬라이딩 윈도우로 탐색하는 과정
맨 왼쪽 글자 해시값 빼주고,
자릿수를 맞춰주고
맨 오른쪽 글자 해시값을 더해주면 된당

자릿수 맞춰주는 부분에서
왜 hash_s = (hash_s + mod) % mod; 이렇게 해주는 지 잘 몰랐었는데
hash_s 가 맨 왼쪽 글자 해쉬값을 빼서 음수가 됐을까바
mod 값을 더해주고 mod로 나눈 것!

c++에서는 -1%4가 -1이기 때문에 3이 나오고 싶으면
(-1 + 4) % 4 같이 해줘야해서 그렇다~~
파이썬은 -1 % 4가 그냥 3이 나오더라!!

근데 first 구해놓는건 잘 이해는 못 했다
그냥 다음에 부분 문자열 구해야 할 일이 있을 때
아~ O(n) 방법이 있었지~~ 그건 라빈 카프씨~~ 이러면서 꺼내 쓰는 정도로 생각해야겠다!

• 이걸 쓸 수 있는 문제 예시
  s, p가 주어질 때 s가 로테이션 된 문자열이 p인가?
  s : abc
  p : bca
  s를 2배 해주고, 거기서 p가 부분 문자열인가 알아보는 문제가 된다! 와-우
  abcabc는 bca가 부분 문자열인가?

코드

#include <iostream>
#include <string>

using namespace std;

int mod = 127;
int base = 256;

//해시값 구하는 함수
//각 문자의 아스키코드에 2^base를 곱해주고
//그 합을 해시값으로 지정
int h(string s) {
	int ans = 0;
	for (auto ch : s) {
		ans = (ans * base + ch) % mod;
	}
	return ans;
}

int main() {
	string s, p;
	cin >> s >> p;

	int sl = s.size();
	int pl = p.size();

	if (sl < pl)
	{
		cout << "0\n";
		return 0;
	}

	int hash_s = h(s.substr(0, pl));
	int hash_p = h(p);
	
	int first = 1;
	for (int i = 0; i < pl - 1; i++) {
		first = (first * base) % mod;
	}

	for (int i = 0; i <= sl - pl; i++)
	{
		if (hash_p == hash_s)
		{
			if (s.substr(i, pl) == p) {
				cout << "1";
				return 0;
			}
		}
		if ((i + pl) < sl)
		{
			hash_s = hash_s - (s[i] * first) % mod; //맨 왼쪽 글자 해시 값 빼주고
			hash_s = (hash_s + mod) % mod; //자릿수 맞춰주고
			hash_s = ((hash_s * base) % mod + s[i + pl]) % mod; //맨 오른쪽 글자 추가해줘
		}

	}
	cout << "0";
}