Newspaper Headline

非常蛋疼的题,做了俩小时,看题解用了一个半小时

给定字符串 s1​ 和 s2​，问至少要用多少个 s1​ 首尾相接拼成新字符串，使得新字符串在删除一些字符后成为 s2​？

感谢@barry_wang 提供的翻译

输入输出样例

abc
xyz

-1

abcd
dabc

2

#include<bits/stdc++.h>
using namespace std;
set<int>g[26];
string s1,s2;
int res=1,p=-1;
int main()
{
    cin>>s1>>s2;//读入
    for(int i=0;i<s1.size();i++) g[s1[i]-'a'].insert(i);//保存每一个字符出现的位置和次数
    for(int i=0;i<s2.size();i++){
        if(g[s2[i]-'a'].empty()){//判断
            cout<<-1;
            return 0;
        }
        if(g[s2[i]-'a'].upper_bound(p)==g[s2[i]-'a'].end()) res++,p=-1;
        //这个地方真的很巧妙,从s2开始找s1的位置,找到第一个符合它的位置,然后接上这个一个字符串
        //举个例子: abcd,cadc,首先c的位置是一开始就会匹配到的,因为初始值为-1,所以第一次循环肯定是找到c
        //此时的字符串可以是abcd,也可以看为cd
        //然后第二次,由于第一次是c的位置,也就是3,我们s2的第二个字符是a,对应s1中的a是第一个位置,那么很明显,我们要在c后面接一个a才行
        //接一个abcd,此时字符串是abcabcdd
        //依次循环就可以了
        p=*g[s2[i]-'a'].upper_bound(p);//每次都要更新要寻找的字符
    }
    cout<<res;
    return 0;
}