hand_01 和 hand_05 寄了

#include <bits/stdc++.h>
using namespace std;

inline void train() {
	   ios::sync_with_stdio(false);
	   cin.tie(0);
	   cout.tie(0);
}

constexpr int N = 1e6+4, G = 4e7+4, INF = 5e7;

constexpr long long MODER1 = 998244353;
constexpr long long MODER2 = 1e9+7;
constexpr int LT = 26;
constexpr char BASE = 'a';

struct hash_data {
	long long first, second;
	hash_data() {
		
	}
	hash_data(string s) : first(0), second(0) {
		for (auto &i : s) {
			first *= LT;
			first += i - BASE;
			first %= MODER1;
			second *= LT;
			second += i - BASE;
			second %= MODER2;
		}
	}
	hash_data(long long data) : first(data % MODER1), second(data % MODER2) {
		
	}
	hash_data(long long first, long long second)
		: first((first + MODER1) % MODER1), second((second + MODER2) % MODER2) {
			
		}
	hash_data operator += (const hash_data &other) {
		first = (first + other.first) % MODER1;
		second = (second + other.second) % MODER2;
		return *this;
	}
	hash_data operator -= (const hash_data &other) {
		first = (first - other.first + MODER1) % MODER1;
		second = (second - other.second + MODER2) % MODER2;
		return *this;
	}
	hash_data operator *= (const hash_data &other) {
		first = (first * other.first) % MODER1;
		second = (second * other.second) % MODER2;
		return *this;
	}
};

bool operator < (const hash_data &a, const hash_data &b) {
	if (a.first == b.first) return a.second < b.second;
	return a.first < b.first;
}

bool operator == (const hash_data &a, const hash_data &b) {
	return a.first == b.first && a.second == b.second;
}

hash_data operator * (const hash_data &a, const hash_data &b) {
	return hash_data(a.first * b.first, a.second * b.second);
}

hash_data operator + (const hash_data &a, const hash_data &b) {
	return hash_data(a.first + b.first, a.second + b.second);
}

hash_data operator - (const hash_data &a, const hash_data &b) {
	return hash_data(a.first - b.first, a.second - b.second);
}


inline int maxi(int a, int b) {
	return a > b ? a : b;
}

inline int mini(int a, int b) {
	return a < b ? a : b;
}

string s,t;
int slen, tlen;
int pre[N], smax[N]; 	// smax[]: destination to reach

//bitset<G> chain_cost;
// For components >= slen consider them on a chain.
deque<int> bfs;
int dis[G];
bitset<G> vis;

hash_data t_hash[N], s_hash[N];
hash_data modding[N];

hash_data operator << (const hash_data &x, int bit) {
	return x * modding[bit];
}

void hash_init(int n) {
	modding[0] = 1;
	for (int i = 1; i <= n; i++) modding[i] = modding[i-1] * LT;
}

// l is not involved !!!
inline hash_data substring(const hash_data &l, const hash_data &r, int len) {
	return (r - (l << len));
}

int main() {

	train();
	
// 	cin>>tlen>>slen;
	cin>>t>>s;
	tlen = t.length(); slen = s.length();
	
	hash_init(maxi(tlen, slen));
	
	t_hash[0] = t[0] - BASE;
	for (int i = 1; i < tlen; i++) t_hash[i] = (t_hash[i-1] * LT) + (t[i] - BASE);
	s_hash[0] = s[0] - BASE;
	for (int i = 1; i < slen; i++) s_hash[i] = (s_hash[i-1] * LT) + (s[i] - BASE);
	
	for (int i = 0; i < slen; i++) {
		int l = i, r = mini(slen, i+tlen-1), ans = -1;
		if (s[i] != t[0]) {
			smax[i] = -1;
//			cerr << "* ";
			continue;
		}
		while (l <= r) {
			int mid = (l+r) >> 1;
			if (substring(((i == 0) ? hash_data(0) : s_hash[i-1]), s_hash[mid], mid-i+1) == t_hash[mid-i]) {
				l = mid + 1;
				ans = mid;
			} else {
				r = mid - 1;
			}
		}
		if (ans != -1) smax[i] = ans + 1;
		else smax[i] = -1;
//		cerr << smax[i] << ' ';
	}
//	cerr << endl;
	
	for (int i = 0; i <= (slen<<1); i++) dis[i] = INF;
	dis[0] = 0;
	bfs.push_back(0);
	while (!bfs.empty()) {
		int front = bfs.front();
//		cerr << "Access " << front << " with distance " << dis[front] << endl;
		bfs.pop_front();
		if (vis[front]) continue;
		vis[front] = true;
		// front = slen: terminated.
		if (front < slen) {
			// Jump to particular point, at 1 cost
			int pdis = dis[front] + 1;
			if (smax[front] == slen) {
				if (pdis < dis[slen]) {
					dis[slen] = pdis;
				}
			} else if (smax[front] >= 0 && (pdis < dis[smax[front] + slen + 1])) {
				dis[smax[front] + slen + 1] = pdis;
				bfs.push_back(smax[front] + slen + 1);
			}
		} else if (front > slen) {	// slen+1 for position 0 in fact !!!
			// Two zero processor
			if (dis[front] < dis[front - slen - 1]) {
				dis[front - slen - 1] = dis[front];
				bfs.push_back(front - slen - 1);
			}
			if (front > (slen+1) && dis[front] < dis[front - 1]) {
				dis[front - 1] = dis[front];
				bfs.push_front(front - 1);
			}
		}
	}
	if (dis[slen] >= INF) cout<<"-1"<<endl;
	else cout<<dis[slen]<<endl;
	
	//cout<<flush;

	return 0;
}