题目链接
大意:给你两个字符串a,b.a是可以无限复制的,现在让你找到一个长度使得这个长度的a串存在一个b的子序列。
思路:如果a字符串包含所有的b中字符,那么必然有解。我们先跑一个a的序列自动机出来。然后每次贪心的匹配b串的字符,如果需要加上a串就加上,否则跳到下一个匹配的位置即可。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[N],b[N];
int F[N],f[N][33];
int vis[33];
int main(){
ios::sync_with_stdio(false);
cin>>a+1>>b+1;
int L=strlen(a+1),R=strlen(b+1);
for(int i=0;i<26;i++)f[L+1][i]=-1;
for(int i=1;i<=L;i++)if(!F[a[i]-'a'])F[a[i]-'a']=i;
for(int i=L;i>=1;i--){
vis[a[i]-'a']=1;
for(int j=0;j<26;j++){
f[i][j]=f[i+1][j];
}
f[i][a[i]-'a']=i;
}
int now=0;
LL ans=0;
for(int i=1;i<=R;i++){
if(!vis[b[i]-'a'])return cout<<-1,0;
if(f[now+1][b[i]-'a']!=-1){
ans+=f[now+1][b[i]-'a']-now;
now=f[now+1][b[i]-'a'];
}else{
ans+=L-now;
ans+=F[b[i]-'a'];
now=F[b[i]-'a'];
}
}
cout<<ans<<endl;
return 0;
}