백준13713 문자열과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/13713

사용 알고리즘

  • Hash
  • Parametric Search

시간복잡도

  • 전처리 O(N)
  • 쿼리 O(log N)

풀이

Z-Algorithm으로 풀 수 있다고는 하는데 제 머리가 좋지 않으므로 해시로 뚫어줍시다.

substring에 대한 해시는 여기를 보고 구현하시면 됩니다.

문제에서 가장 긴 공통 접미사를 구하라고 합니다. 길이를 parametric search로 구해주면 각 쿼리를 O(log N)만에 처리할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct Hashing{
	//1e9-63, 1e9+7, 1e9+9, 1e9+103
	//1e5+3, 1e5+13, 131071, 524287
	vector<ll> hash1, base1;
	ll p, mod;

	Hashing(){
		p = 1e9-63, mod = 524287;
	}

	Hashing(ll _p, ll _mod) : p(_p), mod(_mod) {}

	Hashing(string &s, ll _p, ll _mod) : Hashing(_p, _mod) {
		int n = s.size();
		hash1 = vector<ll>(n+1, 0);
		base1 = vector<ll>(n+1, 0);
		base1[0] = 1; base1[1] = p;
		for(int i=n-1; i>=0; i--){
			hash1[i] = (s[i] + hash1[i+1] * p) % mod;
		}
		for(int i=2; i<=n; i++){
			base1[i] = base1[i-1] * p % mod;
		}
	}

	int substr(int l, int r){ //[s, e]
		ll ret = hash1[l] - hash1[r+1] * base1[r-l+1];
		ret %= mod; ret += mod; ret %= mod;
		return ret;
	}
}h1, h2;

string s; int m;

bool chk(int q, int x){
	if(x == 0) return 1;

	int a = h1.substr(s.size()-x, s.size()-1);
	int b = h1.substr(q-x, q-1);

	int aa = h2.substr(s.size()-x, s.size()-1);
	int bb = h2.substr(q-x, q-1);

	return a == b && aa == bb;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> s >> m;
	h1 = Hashing(s, 1e9-63, 131071);
	h2 = Hashing(s, 1e9+9, 100005);
	while(m--){
		int t; cin >> t;
		int l = 0, r = t, mid;
		while(l <= r){
			mid = l + r >> 1;
			bool now = chk(t, mid);
			bool prv = chk(t, mid+1);
			if(now && !prv) break;
			if(!now) r = mid-1;
			else l = mid+1;
		}
		cout << mid << "\n";
	}
}