まず、\(2\leq i\leq |S|\) をみたす各 \(i\) について、\(S\) の \(i\)文字目から \(|S|\) 文字目までを抜き出した 文字列と \(S\) 自身の最長共通接頭辞の長さ \(f(i)\) を求める事を考えます。これを求めるには Z-Algorithm というものが知られており、\(O(|S|)\) でこれを求めることができます。これは概ね次のようなアルゴリズムです。以下、 \(S\) の \(i\) 文字目を \(S[i]\) で表します。

• \(i=2\)のときは愚直に比較します。すなわち、\(j=1,2,\ldots\) について \(S[j+1]\) と \(S[j]\) を比較し、初めて \(S[j+1]\neq S[j]\) となる\(j\)に対して \(f(2)=j-1\)で定めます。

• \(3\leq i\leq N\) のとき、\(2\leq l\leq i-1\) であって、\(l+f(l)\) が最大となるようなものを取ります。このとき、(\(S\)の \(l\) 文字目から \(l+f(l)-1\) 文字目まで ) \(=\) (\(S\)の \(1\) 文字目か\(らf(l)\) 文字目まで )であるため、(\(S\)の \(i\) 文字目から \(l+f(l)-1\) 文字目まで ) \(=\) (\(S\)の \(i-l+1\) 文字目か\(らf(l)\) 文字目まで )が成り立ちます。

• よって、\(f(i-l+1)<f(l)-(i-l+1)\) であれば\(f(i)=f(i-l+1)\)となります。

• そうでないとき、\(j=1,2,\ldots\) について\(S[l+f(l)-1+j]\) と \(S[l+f(l)-i+j]\) から順に比較していき、初めて \(S[l+f(l)-1+j]\neq S[l+f(l)-i+j]\) となる\(j\)に対して \(f(i)=l+f(l)-i+j-1\)で定めます。

このとき各 \(f(i)\) を求めるのにかかる比較回数は \(\displaystyle\max_{1\leq j\leq i} (f(j)+j)-\displaystyle\max_{1\leq j\leq i-1} (f(j)+j)\) 回程度であることから 全体で \(|S|\) 回程度となる事が分かります。

このアルゴリズムを元に、今回の問題を解くことができます。 \(S\) について 上で述べたような \(f(x)\) は求まっているものとします。

\(g(i)\) で\(T\) の \(1\) 文字目から \(i\) 文字目までの文字列を \(S\) の接頭辞の連結として表したときの最小回数とします。求めたいものは \(g(|T|)\) です。 ただし、表せない場合は \(g(i)=\infty\) とします。ここで、 \(g(i)\) が(広義)単調増加であることに注意します。 まず、 \(g(0)=0\) とし、その後 \(i=1,2,\ldots, |T|\) に対して次のように更新することで、配るDPのような形で順に \(g(i)\) の値を求めます。

• \(i=1\) ならば\(j=1,2,\ldots\) に対して \(S[j]\) と \(T[j]\) を比較し、 \(T[j_0]\neq S[j_0]\) となる最小の \(j_0\) 未満のすべての \(j\) に対し、\(g(j)=1\)とする。

• そうでないとき、\(g(i-1)=\infty\) ならば \(g(i-1)\) は二度と更新されることはなく、最終的にも \(g(N)\geq g(i-1)=\infty\) となるため、ここで打ち切り, \(-1\) を出力します。

• 上のいずれでもない時、ここで行いたいのは、(\(T\)の\(i\)文字目から\(j\) 文字目まで)が (\(S\)の\(1\) 文字目から\(j-i+1\)文字目まで)と一致しているようなすべての\(i\leq j\leq |T|\) について、\(g(j)=\min(g(j),g(i-1)+1)\) と変更する事です。ここで、\(g(i)\) の単調増加性から、\(i\)以前の時点ですでに設定された値は \(g(i-1)+1\)以下であるため、\(g(j)=\infty\) であるようなものに対して\(g(j)=g(i-1)+1\) と変更するだけでよいという事が言えます。

• さて、そのために、\(1\leq r\leq |T|\) であって、\(g(r)<\infty\) となる最大の \(r\)を取ります。また、\(1\leq l\leq i-1\) であって、(\(T\)の \(l\) 文字目から\(r\) 文字目まで )\(=\)(\(S\)の \(1\) 文字目から \(r-l+1\) 文字目まで ) となるようなものが存在するため、そのような \(l\) を取ります。

• (\(T\)の \(i\) 文字目から \(r\) 文字目 ) までは (\(S\)の\(i-l+1\)文字目から \(r-l+1\) 文字目 ) と一致しているため、\(f(i-l+1)<r-i+1\) ならば\(j>r\)に対しては\(g(j)=\infty\) のままなので何も行いません。

• \(f(i-l+1)\geq r-i+1\) のとき、\(j=1,2,\ldots\)について\(T[r+j]\) と \(S[r-i+1+j]\) を比較し、\(T[r+j]\neq S[r-i+1+j]\) となる最小の \(j_0\) 未満のすべての \(j\) に対し、\(g(r+j)=g(i-1)+1\)とする。

このようにして最終的に求まった \(g(|T|)\) を出力すれば良いです。こちらの計算量も比較回数は \(g(r)<\infty\) となる \(r\) の最大値が毎回更新されるので高々 \(O(|T|)\) で、前半のものと合わせて、\(O(|S|+|T|)\) で解くことができました。 これは十分高速です。 c++による実装例

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

int main() {
	string s, t;
	int c[500010], d[500010];
	int l, r;

	cin >> s;
	cin >> t;
	int n = s.size();
	int m = t.size();

	r = 1;
	c[0] = n;
	for (int i = 1; i < n; i++) {
		if (r == n)c[i] = n - i;
		if (i == 1) {
			while (r < n) {
				if (s[r] == s[r - i])r++;
				else break;
			}
			c[i] = r - i;
			l = i;
		}
		else if (c[i - l] < (r - i)) {
			c[i] = c[i - l];
		}
		else {
			r = max(i, r);
			while (r < n) {
				if (s[r] == s[r - i])r++;
				else break;
			}
			c[i] = r - i;
			l = i;
		}
	}

	for (int i = 0; i < m; i++)d[i] = -1;
	r = 0;
	for (int i = 0; i < m; i++) {
		if (r == m)break;
		if (i == 0) {
			while ((r < m) && (r < n)) {
				if (t[r] == s[r]) {
					d[r] = 1;
					r++;
				}
				else break;
			}
			l = 0;
		}
		else if (d[i - 1] == -1)break;
		else if (c[i - l] >= r - i) {
			while ((r < m) && ((r - i) < n)) {
				if (t[r] == s[r - i]) {
					d[r] = d[i - 1] + 1;
					r++;
				}
				else break;
			}
			l = i;
		}
	}
	cout << d[m - 1] << endl;

	return 0;
}