글 읽기 - pow 함수를 이용하면 시간복잡도가 많이 커지나요??

shinbian11 3년 전 0

pow 함수는 실수에 관련된 작업이라 오래 걸린다고는 대충 알고 있엇는데, hash_val 함수 내부를 밑처럼 구현하면 시간초과가 나는데, pow함수가 오래 걸려서 인가요? 물론 이때 len은 m의 길이입니다.

int ans = 0;
len -= 1;
for (char s : str)
{
ans += (int)(s * pow(base, len)) % mod;
ans %= mod;
len--;
}
return ans;

#include <bits/stdc++.h>
#define F_I ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;

ll Min(ll a, ll b) { return (a < b) ? a : b; }
ll Max(ll a, ll b) { return (a < b) ? b : a; }
ll gcd(ll m, ll n) { if (n == 0) return m; return gcd(n, m % n); } //최대공약수
ll lcm(ll m, ll n) { return m * n / gcd(m, n); } //최소공배수

int mod = 127;
int base = 256;


int hash_val(string str)
{
	int ans = 0;
	for (char ch : str) //pow()를 통해 하는 것 보다 이런 방법으로 하기!
	{
		ans = (ans * base + ch) % mod;
	}
	return ans;
}

int match(string& a, string& b)
{
	int n = a.length();
	int m = b.length();

	if (n < m)
		return 0;

	int pattern = hash_val(b); //찾고자 하는 패턴의 hash 값 구하기

	int f = hash_val(a.substr(0, m)); //문자열의 첫번째 덩어리의 hash 값 구하기 (두번째 덩어리부터는 그 전 덩어리에서 구했던 hash값의 일부분을 이용)

	int first = 1; 

	for (int i = 0; i < m - 1; i++)
		first = (first * base) % mod; //pow(base, m-1) 말고 이 방법으로 하기!

	for (int i = 0; i <= n - m; i++)
	{
		if (f == pattern) //hash 값이 같으면
		{
			if (a.substr(i, m) == b) return 1; //같은 문자열인지 확인
		}
		else
		{
			if (i + m < n) // i+m >= n 이면, a[i+m] 부분에서 배열 메모리 참조 오류 생기니까!
				f = ((((f - ((int)(a[i] * first) % mod)) * base) % mod) + a[i + m]) % mod;
		}
	}
	return 0;
}
int main()
{
	F_I;
	string n, m;
	cin >> n >> m;
	cout << match(n, m) << '\n';
	return 0;
}

slah007 3년 전 0

pow(n, k) mod m 를 lg k 만에 구할 수 있습니다.

shinbian11 3년 전 0

그럼 얼마 안 걸리는 거 아닌가요? logk 에서 밑이 2고 k가 최대 100만인데, 그럼 20 이하의 값이 나오는데...

그럼 hash_val 함수 내부를 pow로도 구현 가능한가요?

jhnah917 3년 전 1

mod가 너무 작습니다. mod가 127인 경우 1/127의 확률로 `a.substr(i, m) == b`를 호출하게 됩니다.

평균적으로 `(문자열 길이)^2 / 127` 정도의 연산량을 요구하는데, 문자열의 길이가 최대 100만이기 때문에 TLE가 나기 쉽습니다.

shinbian11 3년 전 0

감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

pow 함수를 이용하면 시간복잡도가 많이 커지나요??

shinbian11 3년 전 0

slah007 3년 전 0

shinbian11 3년 전 0

jhnah917 3년 전 1

shinbian11 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말