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

题目链接
大意：给你两个字符串a,b.a是可以无限复制的，现在让你找到一个长度使得这个长度的a串存在一个b的子序列。
思路：如果a字符串包含所有的b中字符，那么必然有解。我们先跑一个a的序列自动机出来。然后每次贪心的匹配b串的字符，如果需要加上a串就加上，否则跳到下一个匹配的位置即可。

#include#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_backusing 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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！