https://codeforces.com/contest/91/problem/A
输入长度不超过 1e4 的字符串 s1 和长度不超过 1e6 的字符串 s2,都只包含小写字母。
设字符串 t = s1 * x 表示由 s1 重复 x 次的字符串,比如 “abc” * 3 = “abcabcabc”。
输出使 s2 是 t 的子序列的 x 的最小值。如果无法做到输出 -1。
注:子序列不一定是连续的。
输入
abc
xyz
输出 -1
输入
abcd
dabc
输出 2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
const int N = 10010;
int ne[N][26];
void solve()
{
memset(ne, -1, sizeof ne);
string s1, s2;
cin >> s1 >> s2;
for(int i = s1.size() - 1; i >= 0; i --){
for(int j = 0; j <= 25; j ++)
{
int c = s1[i] - 'a';
if(c == j) ne[i][j] = i;
else ne[i][j] = ne[i + 1][j];
}
}
int t = 0;
int res = 1;
for(int i = 0; i < s2.size(); i ++)
{
int c = s2[i] - 'a';
if(ne[0][c] == -1){
puts("-1");
return;
}
else if(ne[t][c] == -1){
i --;
t = 0;
res ++;
}
else{
t = ne[t][c] + 1;
if(t == s1.size()){
t = 0;
if(i < s2.size() - 1) res ++;
}
}
}
cout << res << endl;
}
int main ()
{
int T = 1;
while(T --){
solve();
}
return 0;
}