백준1235 학생 번호

작성일 | In

문제 링크

  • http://icpc.me/1235

사용 알고리즘

  • Hashing

시간복잡도

  • O(N * len)

풀이

각 문자열마다 최대 100개나 되는 suffix를 모두 naive하게 비교해도 됩니다.
그러나 suffix를 해싱해서 비교하면 더 빠르게 비교할 수 있습니다.

개인적으로 문자열의 개수를 1000개, 각 문자열의 길이를 10000까지로 범위를 늘리는 것도 좋을 것 같습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll b1 = 23, b2 = 59, b3 = 17;
const ll p1 = 1e9+7, p2 = 1e9+9, p3 = 1e9-63;

struct Hash{
	ll a, b, c;

	bool operator == (Hash &x){
		return a == x.a && b == x.b && c == x.c;
	}
	bool operator < (const Hash &x)const{
		if(a != x.a) return a < x.a;
		if(b != x.b) return b < x.b;
		return c < x.c;
	}
};

vector<Hash> arr;
vector<string> v;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; v.resize(n); arr.resize(n+1);
	for(int i=0; i<n; i++) cin >> v[i];
	int len = v[0].size();

	int cnt = 0;

	for(int i=len-1; i>=0; i--){
		set<Hash> s;
		cnt++;
		for(int j=0; j<n; j++){
			arr[j].a = (arr[j].a * b1 + v[j][i]) % p1;
			arr[j].b = (arr[j].b * b2 + v[j][i]) % p2;
			arr[j].c = (arr[j].c * b3 + v[j][i]) % p3;
			s.insert(arr[j]);
		}
		if(s.size() == n){
			cout << cnt; return 0;
		}
	}
}