1295-C, *1600

Problem - C - Codeforces

문제

• 문자열 s, t 가 주어진다
• s의 subsequence 를 몇 번을 더해야 t 와 같은 문자열이 될까?

 

$O(|s|log\ |s|)$

s 의 각 알파벳별로 index 를 map loc 에 저장해놓는다
빨간색 포인터의 다음 위치는 loc[알파벳]에서 이진탐색을 이용하여 구한다
빨간색 포인터가 ind |s| 까지 가거나, 찾으려는 알파벳이 없으면 초기값 ps = -1 으로 갱신하고
cnt 값을 하나 증가킨다

#include <bits/stdc++.h>
#define endl "\n"
#define ooop(i, n) for(int i = 0; i < n; i++)
#define loop(i, n) for(int i = 1; i <= n; i++)
#define all(v) (v).begin(), (v).end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        string s, t;
        cin >> s >> t;
        map<char, vector<int> > loc;
        ooop(i, s.size()) loc[s[i]].emplace_back(i);
 
        bool avail = true;
        ooop(i, t.size()){
            if(loc.find(t[i]) == loc.end()){
                avail = false;
                break;
            }
        }
 
        if(avail){
            int pt = 0;
            int cnt = 0;
            int ts = static_cast<int>(t.size());
            int ss = static_cast<int>(s.size());
            while(pt < ts){
                int ps = -1;
                while(ps < ss){
                    auto ind = lower_bound(all(loc[t[pt]]), ps+1) - loc[t[pt]].begin();
                    if(ind == loc[t[pt]].size()) break;
                    else{
                        ps = loc[t[pt]][ind];
                        pt++;
                    }
                }
                cnt++;
            }
            cout << cnt << endl;
        }
        else cout << -1 << endl;
    }
 
    return 0;
}cs

※ unsign int 와 signed int 를 비교할 때 조심!

static_cast<int> 이용한다