原题链接
考察:贪心+思维
思路:
??首先明确抹去字符不能改变\(s1\)在\(s2\)的位置.也就是不存在\("你中有我,我中有你"\)的情况.所以如果\(s2[i]\)在\(s1[i]\)出现位置比\(s2[i+1]\)晚,那么\(ans++\).
??两层\(for\)循环明显需要优化,所以预处理\(s1\)的情况.\(f[i][j]\)表示\(s1\)下,索引是\(i\),往右字母是\(j+‘a‘\)的下标.然后就是双指针.
Code
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10010,M = 1000010,S = 30;
char a[N],b[M];
int alen,blen,d[N][S],ans;
bool vis[S];
int main()
{
scanf("%s%s",a,b);
alen = strlen(a),blen = strlen(b);
memset(d,-1,sizeof d);
for(int i=0;i<alen;i++)
{
vis[a[i]-‘a‘] = 1;
//在j右边,s[i]最近在哪个位置
for(int j=0;j<=i;j++)
if(d[j][a[i]-‘a‘]==-1)
d[j][a[i]-‘a‘] = i;
}
bool ok = 1;
for(int i=0;i<blen;i++)
if(!vis[b[i]-‘a‘]) ok = 0;
if(!ok)
{
puts("-1");
return 0;
}
for(int i=0;i<blen;)
{
int j = 0;
while(j<alen&&i<blen&&d[j][b[i]-‘a‘]!=-1)
{
j = d[j][b[i]-‘a‘]+1;
i++;
}
ans++;
}
printf("%d\n",ans);
return 0;
}