AtCoder Beginner Contest 138 E - Strings of Impurity(序列自动机)

题目链接
大意：给你两个字符串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;
}