题解：CF91A Newspaper Headline

_WHX985_ · 2025-02-05 12:10:22 · 题解

题意

输入两个字符串 s_1 和 s_2 问构成 s_2 至少需要几个 s_1。

思路

虽然用 set 和 vector 也可以，但这样用的知识点较多，所以今天介绍的是本题最见做法，直接枚举。输入后首先看有没有 s_2 字符串有的字符但 s_1 字符串没有，这种情况输出 -1 因为无论拼多少个 s_1 字符串也不会有这个字符。如果没有这样的字符就一个一个找。

代码

#include<bits/stdc++.h>
#define l size()-1
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define fd(i,r,l) for(int i=r;i>=l;i--)
using namespace std;
int dp[27][10005];
int lpos,pos,ans=1;
string s1,s2;
map<char,bool>mp;
int main(){
    cin>>s1>>s2;
    fo(i,0,s1.l)mp[s1[i]]=1;
    fo(i,0,s2.l)
        if(!mp[s2[i]])return cout<<-1,0;
    fo(i,0,25)
        if(mp[i+'a']){
            int tmp=s1.l+1;
            fd(j,s1.l,0){
                if(s1[j]==i+'a')tmp=j;
                dp[i][j]=tmp;
            }
            fo(j,0,s1.l)
                if(dp[i][j]==s1.l+1)dp[i][j]=tmp;
        }
    fo(i,0,s2.l){
        if(s2[i]==s2[(i+s2.l)%s2.size()]){
            lpos=pos;
            pos=dp[s2[i]-'a'][(pos+1)%s1.size()]; 
        }
        else{
            lpos=pos;
            pos=dp[s2[i]-'a'][pos];
        }
        if(pos<=lpos)ans++;
    }
    cout<<ans;
    return 0;
}