티스토리 뷰

알고리즘 관련/BOJ

BOJ)14965 Lozinke

JASON 자손9319 2018. 6. 26. 02:03

문제: icpc.me/14965


n개의 문자열이 주어질 때, 모든 문자열 s에 대해, s의 substring 중에 현재 보는 문자열을 제외한 나머지 문자열이 되는 개수를 전부합하여 출력하는 문제이다.


직접 비교하면 n^2으로 시간초과를 보게된다.


문자열의 길이가 10이하라는 사실을 이용하여 모든 문자열 s를 해싱해준 뒤


마찬가지로 모든 문자열의 substring을 전부 해싱하여 set과 map을 이용하여 개수를 계산해주면 n*10*10*logn의 시간에 문제를 해결할 수 있다.


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
#include <cstdio>
#include <algorithm>
#include <string>
#include <iostream>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
const ll mod=1e9+223;
const ll mod2=1e9+7;
map<pair<ll,ll>,ll> mp;
ll n,res;
string s[20002];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>s[i];
        ll hash=0;
        ll hash2=0;
        for(auto next:s[i]){
            hash*=27LL;
            hash2*=27LL;
            hash%=mod;
            hash2%=mod2;
            hash+=(next-'a'+1)*1LL;
            hash2+=(next-'a'+1)*1LL;
            hash%=mod;
            hash2%=mod2;
        }
        mp[{hash,hash2}]++;
    }
    for(int i=0;i<n;i++){
        set<pair<ll,ll>> cs;
        for(int j=0;j<s[i].length();j++){
            ll hash=0;
            ll hash2=0;
            for(int k=j;k<s[i].length();k++){
                hash*=27LL;
                hash2*=27LL;
                hash%=mod;
                hash2%=mod2;
                hash+=(s[i][k]-'a'+1)*1LL;
                hash2+=(s[i][k]-'a'+1)*1LL;
                hash%=mod;
                hash2%=mod2;
                if(mp.find({hash,hash2})!=mp.end())cs.insert({hash,hash2});
            }
        }
        ll curr=0;
        for(auto next:cs)
            curr+=mp[next];
        res+=curr-1;
    }
    cout<<res;
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13274 수열  (0) 2018.07.02
BOJ)15589 Lifeguards (Silver)  (0) 2018.06.26
BOJ)14965 Lozinke  (0) 2018.06.26
BOJ)11964 Fruit Feast  (0) 2018.06.25
BOJ)11046 팰린드롬??  (0) 2018.06.25
BOJ)1222 홍준 프로그래밍 대회  (0) 2018.06.25
TAG
댓글
댓글쓰기 폼