[그리디, 난이도 중] 백준 1543번 문서 검색

문자열 매칭 알고리즘들중 라빈카프를 이용했다.

라빈카프 알고리즘은 문자열의 특정 해쉬값을 계산한 후 두 해쉬값이 일치할 경우, 문자열 매칭에 성공했다고 판단하는 알고리즘이다. 여기서 2차적으로 동일한 해쉬값을 가진 문자열에 대해서 확인차로 한번더 문자열 그 자체를 검사할 수도있다. 

 

문자열의 해쉬값을 정하는 방법은 많지만 이 소스코드에서 해쉬값은 이렇게 정했다.

문자열 a의 size를 size라고 가정하면

문자열의 해쉬값 = a[0]*2^(size-1) + a[1]*2^(size-2) +a[2]*2^(size-3) + ... a[size-1]*2^0

 

https://www.youtube.com/watch?v=kJJQJDsjXc8

 

문자열 매칭 알고리즘은 동빈나 님의 강의로 배웠는데

여기서 동빈나님이 이용하신 라빈카프 알고리즘은 문자열 중복을 허용했다.

즉 ababababa 에서 aba 문자열을 찾을때 인덱스 0,2,4,6 인덱스에서 찾았다고 할 것이라는 의미이다.

하지만 백준 1543번 문서 검색에서는 중복문자열을 허용하지 않고 0,4 인덱스에서 찾았다고 판단하는 것을 원한다.

그래서 소스코드중 일부를 바꾸었다.

 

아래 소스코드에서 int p=-1; 로 정의한 것이있는데 아직 매칭을 하지 않았다는 의미로 -1로 초기화했다.

p는 parent배열에서 최근 매칭 성공한 부분의 끝 인덱스이다.

예를들어 abcdefg 에서 cde를 찾는다고 했을 때

parent의 cde부분 즉, 인덱스 2~4부분에서 매칭이 이루어졌는데 여기서 매칭 성공한 부분의 끝 인덱스는 4이다.

 

이렇게 p=4로 갱신해주고 다음에 매칭에 성공 하였더라도, 만약 매칭 성공한 부분의 첫 문자열인덱스가 p이하라면 이는 중복되었다는 의미이므로 아무처리도 하지 않으면 문제는 해결된다.

 

 

#include <iostream>
#include <string.h>
#include <string>
using namespace std;
int ans, parenthash, patternhash;
void findstring(string parent, string pattern) {
	int parentsize = parent.size();
	int patternsize = pattern.size();
	int power = 1;
	int p = -1;
	
	for (int i = 0; i < patternsize; i++) {
		parenthash += parent[patternsize - 1 - i] * power;
		patternhash += pattern[patternsize - 1 - i] * power;
		if (i < patternsize - 1) power *= 2;
	}
	
	for (int i = 0; i <= parentsize - patternsize; i++) {
		if(i) parenthash = 2 * (parenthash - parent[i - 1] * power) + parent[patternsize - 1 + i];
		if (parenthash == patternhash) {
			bool found = true;
			for (int j = 0; j < patternsize; j++) {
				if (parent[i + j] != pattern[j]) {
					found = false;
					break;
				}
			}
			if (found && p<i) {
				ans++;
				p = i+patternsize-1;
			}
		}
	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string a, b;
	getline(cin, a);
	getline(cin, b);
	findstring(a, b);
	cout << ans;
}