[백준/BOJ/1786] 찾기

원래 정석의 라빈카프로 접근해야 했다면 hash 값이 똑같을 때, 하나씩 문자 비교하는 작업이 필요하다.

그러나 hash 함수를 매우 잘 짜면 기도메타 방법으로 문자 비교하지 않고 index 만 저장하는 방식으로 해결 가능하다.

 

1번 코드는 정석 방법 (35% 에서 시간 초과)

2번 코드는 기도메타 방법 (통과)

3번 코드는 해시를 2개 쓰는 방법이다. 확률 변수가 하나 더 추가 되기 때문에 이 방법이 정 해 일 가능성이 높다.

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = (1L << 31) -1;
const int MAX = 1e6+1;
//char S[MAX],W[MAX];
string S,W;
inline ll __mod(ll n){
	if(n>=0) return n%MOD;
	return ((-n/MOD+1)*MOD+n)%MOD;
}
int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//gets(S);
	//gets(W);
	
	std::getline(std::cin,S);
	std::getline(std::cin,W);
	ll N = S.size();
	ll M = W.size();
	ll SH = 0;
	ll WG = 0;
	ll power = 1;
	ll res = 0;
	vector<int> v;
	for(int i=0;i<=N-M;i++){
		if(i==0){
			for(int j=0;j<M;j++){
				WG = __mod(WG+1LL*W[M-1-j]*power);
				SH = __mod(SH+1LL*S[M-1-j]*power);
				if(j<M-1) power=__mod(power*7);
			}
		}
		else{
			SH = __mod(7*(SH-1LL*S[i-1]*power))+S[i+M-1];
		}
		if(WG==SH){
			bool flag=true;
			for(int j=0;j<M;j++){
				if(S[i+j] != W[j]){
					flag=false;
					break;
				}
			}
			if(flag) {
				v.push_back(i+1);
			}
		}
	}
	cout<<v.size()<<"\n";
	for(int i=0;i<v.size();i++){
		cout<<v[i]<<" ";
	}
	return 0;
}

 

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const ll MOD = 1e9+7;
const int MAX = 1e6+1;
//char S[MAX],W[MAX];
string S,W;
inline ll __mod(ll n){
	if(n>=0) return n%MOD;
	return ((-n/MOD+1)*MOD+n)%MOD;
}
int main(){	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	//gets(S);
	//gets(W);
	
	std::getline(std::cin,S);
	std::getline(std::cin,W);
	ll N = S.size();
	ll M = W.size();
	ll SH = 0;
	ll WG = 0;
	ll power = 1;
	ll res = 0;
	vector<int> v;
	for(int i=0;i<=N-M;i++){
		if(i==0){
			for(int j=0;j<M;j++){
				WG = __mod(WG+1LL*W[M-1-j]*power);
				SH = __mod(SH+1LL*S[M-1-j]*power);
				if(j<M-1) power=__mod(power*31);
			}
		}
		else{
			SH = __mod(31*(SH-1LL*S[i-1]*power))+S[i+M-1];
		}
		if(WG==SH){
			v.push_back(i+1);
		}
	}
	cout<<v.size()<<"\n";
	for(int i=0;i<v.size();i++){
		cout<<v[i]<<" ";
	}
	return 0;
}

#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int MAX = 1e6 + 1;
string T, P;
vector<int> loc;
ll __mod(ll a) {
	if (a >= 0) return a % MOD;
	return ((-a / MOD + 1)*MOD + a) % MOD;
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	std::getline(std::cin, T);
	std::getline(std::cin, P);
	int N = T.size();
	int M = P.size();
	ll th1 = 0, th2 = 0;
	ll ph1 = 0, ph2 = 0;
	ll pwr1 = 1, pwr2 = 1;
	for (int i = 0; i <= N-M; i++) {
		if (i == 0) {
			for (int j = 0; j < M; j++) {
				th1 = __mod(th1 + 1LL * pwr1*T[M-1-j]);
				ph1 = __mod(ph1 + 1LL * pwr1*P[M - 1 - j]);
				th2 = __mod(th2 + 1LL * pwr2*T[M-1-j]);				
				ph2 = __mod(ph2 + 1LL * pwr2*P[M-1-j]);
				if (j < M - 1) {
					pwr1 = __mod(pwr1 * 3);
					pwr2 = __mod(pwr2 * 7);
				}
			}
		}
		else {
			th1 = __mod(3 * (th1 - 1LL * pwr1*T[i - 1]) + T[i+M-1]);
			th2 = __mod(7 * (th2 - 1LL * pwr2*T[i - 1]) + T[i+M-1]);
		}
		if (th1 == ph1 && th2 == ph2) {
			loc.push_back(i+1);
		}		
	}
	cout << loc.size() << "\n";
	for (auto idx : loc) {
		cout << idx << " ";
	}
	cout << "\n";
	return 0;
}