[백준 20191] 줄임말

문제

www.acmicpc.net/problem/20191

 

알고리즘

이분탐색

 

풀이

문자열 S와 T가 주어집니다. $T^n$을 문자열 T를 n회 반복한 문자열이라고 정의할 때, n번 반복하여 줄임말 S를 만들기 위한 최소 n을 구하는 문제입니다.

 

줄임말을 만들 때, 순서를 유지한다는 점에서 투포인터 전략을 떠올릴 수 있습니다. 각각을 $pt, ps$라고 해봅시다. 각 포인터가 가리키는 문자열이 일치할 때는 둘 다 1씩 더해서 다음 문자를 확인하고 다르다면 $pt$만을 증가시키고 문자열 T가 끝에 다다랐다면 다시 $pt$를 0으로 초기화 해줍니다.

 

이렇게 할 경우 다음과 같은 예시에서 비효율적으로 작동하게 됩니다.

 

zzzz

aaaz

 

즉 z가 나타나는 위치를 찾기 위해 일일이 T문자열을 탐색하는 대신, 다른 전략을 사용해야 합니다.

 

이차원 벡터를 활용해 T에서 각 문자가 등장하는 인덱스를 벡터에 순차적으로 담아봅시다. 현재 처리해야하는 문자에 해당하는 벡터에서 pt의 값을 이분탐색하여 다음에 처리해야할 문자가 어디서 등장하는지 찾게 되면 일일이 찾는 것보다 훨씬 빠른속도로 찾을 수 있습니다.

 

문자열 S마다 최대 T의 길이만큼 이분탐색하므로 시간복잡도는 $O(SlogT)$입니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

string s, t;

vector<int> alpha[26];
int ans = 1, ps, pt, tl, sl;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> s >> t;
    sl = s.size();
    tl = t.size();
    rep(i, tl) {
        alpha[t[i] - 'a'].emplace_back(i);
    }
    while (ps < sl) {
        int x = s[ps] - 'a';
        if (alpha[x].empty()) {
            cout << -1;
            exit(0);
        }

        int pos = lower_bound(alpha[x].begin(), alpha[x].end(), pt) - alpha[x].begin();
        if (pos >= alpha[x].size()) {
            ans += 1;
            pos = 0;
        }
        pt = alpha[x][pos];
        pt += 1;
        ps += 1;
    }
    cout << ans;
    return 0;
}