"map병장 메모리제한에 패배"

 

웃기네여

---

https://www.acmicpc.net/problem/27652

27652번: AB

---

2023 성균관대학교 프로그래밍 경진대회를 미는 중에 만난 문제이다.

 

풀이

그냥 하면 될 거라 생각해서 풀었다. 쿼리 들어올 때마다 접미사, 접두사를 관리하는 map을 관리하면 해결할 수 있다.

이렇게 짜면, $O(Q|S|log(Q|S|))$ 정도의 시간이 걸린다. 최악 $1000*1000*20$ 정도의 시간이 걸린다.

이 풀이를 내면 MLE를 받을 수 있는데, MLE를 받고 나서 해싱을 이용하면 문자열을 들고다니는 대신 정수 하나만 들고 다닐 수 있어서 MLE를 해결할 수 있을거라 생각해서 해싱을 추가했다.

이러면, TLE를 받을 수 있다.

어디선가 본, unordered_map이 떠올라서 map 대신 사용했다. 이러니 TLE가 해결되었다..

다른 사람 코드도 구경 좀 해보니, map으로도 가능한 듯 하네요. 그냥 제 해싱이 무거운 듯 합니다.

근데 또 솔루션 보니 Trie가 정해라고 하던데, 그게 맞는 듯 합니다 ㅋㅋ

 

코드

ll q, idx, len, ans;
string a, b, s;
unordered_map<ll, ll> mp[2];

template<ll P, ll M> struct Hashing
{
	vector<ll> H, B;
	void build(const string& S)
	{
		H.resize(S.size() + 1);
		B.resize(S.size() + 1);
		B[0] = 1;
		for (int i = 1; i <= S.size(); i++) H[i] = (H[i - 1] * P + S[i - 1]) % M;
		for (int i = 1; i <= S.size(); i++) B[i] = B[i - 1] * P % M;
	}
	ll get(int s, int e)
	{
		ll res = (H[e] - H[s - 1] * B[e - s + 1]) % M;
		return res >= 0 ? res : res + M;
	}
};

void solve()
{
	cin >> q;
	while (q--)
	{
		cin >> a >> b;
		if (a == "add")
		{
			cin >> s;
			len = s.length();
			Hashing<524287, 998244353> H;
			H.build(s);
			idx = b == "A" ? 0 : 1;
			for (int i = 1; i <= len; i++)
				if (idx == 0) mp[idx][H.get(1, i)]++;
				else mp[idx][H.get(i, len)]++;
		}
		else if (a == "delete")
		{
			cin >> s;
			len = s.length();
			Hashing<524287, 998244353> H;
			H.build(s);
			idx = b == "A" ? 0 : 1;
			for (int i = 1; i <= len; i++)
				if (idx == 0) mp[idx][H.get(1, i)]--;
				else mp[idx][H.get(i, len)]--;
		}
		else if (a == "find")
		{
			ans = 0;
			len = b.length();
			Hashing<524287, 998244353> H;
			H.build(b);
			for (int i = 1; i <= len; i++) // [0...i], [i+1...len-1]
				ans += mp[0][H.get(1, i)] * mp[1][H.get(i + 1, len)];
			cout << ans << '\n';
		}
	}
}

 

작년 여름 신촌 중급 캠프에서 해싱 배운 이후로 해싱을 단 한번도 만나본 적이 없었는데, 이렇게 해싱을 쓰게 되어서 뿌듯했네요!