[도전 1일차] 10840 구간 성분

문제 : BOJ 10840 구간 성분 

문제 링크

 

사용 알고리즘 : 1. STL set 2.해싱

풀이: 

1. STL set을 사용한 풀이

각 부분 문자열에 대한 알파벳 개수를 벡터를 이용해 센다. 

이때 문자열에서 길이별로 슬라이딩 윈도우를 이용해 개수를 빠르게 구해준다. 

1번째 문자열에서는 크기 26의 벡터로 알파벳의 개수를 저장하고 set에 넣어준다. 

2번째 문자열에서도 벡터를 구한 다음 set에서 확인한다. 이때 길이를 큰 것부터 확인하면 탐색 공간 배제가 가능하다.

 

2. 해싱을 사용한 풀이

각 알파벳을 소수에 대응한다. 각 부분 문자열에 대한 '구간 성분 값'은 소수의 곱을 mod 한 결과로 대응한다. 이때 해시 충돌 가능성이 있으므로, 다른 알파벳을 소수에 대응하여 이중 해싱을 해준다. (즉, 소수를 52개 이상 구해준다.)

해시값은 vector<pair<int,int>> Hash[ mod ]에 저장한다.

x : 1번째 해시값, y: 2번째 해시값이라 할때

Hash[x] . push_back( y, len)과 같이 하고,

for(auto& p: Hash[x] ) if (p == make_pair(y,len) ) ans= max(ans,len);

으로 답을 갱신해준다.

 

* 소수는 52개만 구하면 되므로 에라토스테네스의 체는 필요없다. 6k +- 1로도 충분하다.

 

Code

//pentagon@sasa.hs.kr 
#include<bits/stdc++.h>
#define ll long long
const int INF = 1e9;
using namespace std;
int ans;
set<vector<int>> S;
int main(){
    ios::sync_with_stdio(false); cin.tie(0);
    string s1,s2;
    cin>>s1>>s2;
    int L1=s1.length(),L2=s2.length();
    int L=min(L1,L2);
    for(int i=1;i<=L;i++){
        vector<int> cnt(26);
        int s=0,e=i-1;
        for(int j=s;j<=e;j++)
            cnt[s1[j]-'a']++;
        while(e<L1){
            S.insert(cnt);
            if(++e<L1){
                ++cnt[s1[e]-'a'];
                --cnt[s1[s++]-'a'];
            }
        }
    }
    for(int i=L;i>=1;i--){
        vector<int> cnt(26);
        int s=0,e=i-1;
        for(int j=s;j<=e;j++)
            cnt[s2[j]-'a']++;
        while(e<L2){
            if(S.count(cnt)>0){
                cout<<i;
                return 0; 
            }
            if(++e<L2){
                ++cnt[s2[e]-'a'];
                --cnt[s2[s++]-'a'];
            }
        }
    }
    cout<<0;
}