题目链接
题意：串S，T，T是目标串，你需要将一个空串变成T，通过将S的任意子串添加到这个要变成T的串后头，这里的子串可以是不连续的，问最少次数，做不到就-1
讲道理做这种题目没技巧，就是很直接，但是要认真分析出来，你要添加一个字符就去S里找最早出现的嘛，贪心很好理解，然后下一个字符看看有没有在这个最早出现位置的后头，要是有，ok接着如上操作否则答案 1，无解的情况很简单就是没有这个字符嘛
这样还不够要是极端样例会卡不过，很明显要用二分查找，就是先遍历一遍字符串找出每个字母的出现下标位置，这样就保证每一个字母出现位置都是有序的，就可以快速查找，嗯差不多就这样，详见代码
代码语言：javascript复制#include<bits/stdc .h>
using namespace std;
#define ll long long
#define rg register ll
int main()
{
ll n;
cin>>n;
for(rg i=1;i<=n;i )
{
string s,t;
vector<ll>v[30];
cin>>s>>t;
for(rg j=0;s[j];j )
{
v[s[j]-'a'].push_back(j);
}
ll ans=1,tep=-1;
for(rg j=0;t[j];j )
{
ll k=t[j]-'a';
if(!v[k].size())
{
ans=-1;
break;
}
else
{
if(v[k][v[k].size()-1]>tep)
{
//cout<<*upper_bound(v[k].begin(),v[k].end(),tep)<<endl;
tep=v[k][upper_bound(v[k].begin(),v[k].end(),tep)-v[k].begin()];
}
else ans ,tep=v[k][0];
}
}
cout<<ans<<endl;
}
while(1)getchar();
return 0;
}
