题解归档 - cf104114A

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114A
• 本地来源：problems/cf104114A/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/A
• 原始标题：cf104114A - AppendAppendAppend

思路

cf104114A - AppendAppendAppend

Need the first day d such that t is a subsequence of s repeated d times.

For every character, store all positions in one copy of s. Scan t greedily while keeping the next usable position cur in the current copy:

• if the character appears at some position >=cur, use the first such position;
• otherwise move to the next copy/day and use the first occurrence of that character.

Greedy is optimal for subsequence matching because using the earliest possible occurrence leaves the maximum suffix for later characters.

Complexity: O((|s|+|t|) log |s|), alphabet is 26.

代码

来源：problems/cf104114A/solution.cpp

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s,t;
    cin>>s>>t;

    vector<int> pos[26];
    for(int i=0;i<(int)s.size();i++) pos[s[i]-'a'].push_back(i);

    ll ans=1;
    int cur=0;
    for(char ch:t){
        auto &v=pos[ch-'a'];
        auto it=lower_bound(v.begin(),v.end(),cur);
        if(it==v.end()){
            ans++;
            cur=v[0]+1;
        }else{
            cur=*it+1;
        }
    }
    cout<<ans<<"\n";
    return 0;
}