백준20191 줄임말

작성일 | In

문제 링크

  • http://icpc.me/20191

문제 출처

  • 2020 KOI 고등부 1번

시간복잡도

  • $O(\vert S \vert \log \vert T \vert)$

풀이

$T$의 $i$번째 글자 이후에 처음으로 문자 $c$가 등장하는 위치를 $f_c(i)$로 정의합시다.
$f_c(i)$를 빠르게 계산할 수 있다면, $f_{S_0}(0)$, $f_{S_1}(f_{S_0}(0))$, $f_{S_2}(f_{S_1}(f_{S_0}(0))$를 따라가면서, $T$를 몇 번 순회하는지 구하는 것으로 문제를 해결할 수 있습니다.

$T$에서 각 문자가 등장하는 인덱스를 정렬된 상태로 저장하면, 이분 탐색을 이용해 $f_c(i)$를 $O(\log \vert T \vert)$에 계산할 수 있으므로, $O(\vert S \vert \cdot \log \vert T \vert)$에 문제를 해결할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

string s, t;
vector<int> g[256];

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> s >> t;
    for(int i=0; i<t.size(); i++) g[t[i]].push_back(i);
    for(auto i : s) if(g[i].empty()){ cout << -1; return 0; }

    int pos = -1, cnt = 1;
    for(auto i : s){
        auto it = lower_bound(all(g[i]), pos+1);
        if(it == g[i].end()) cnt++, it = g[i].begin();
        pos = *it;
    }
    cout << cnt;
}