\(R_i\) の \(j\) 文字目は \(S\) の \((i+j) \bmod N\) 文字目です。 \(\bmod\) の処理は難しいですが、これは \(S\) を長さが \(2N+M\) 以上になるように自分自身を連結させた文字列 \(S'\) の \(i+j\) 文字目となります。

また、この \(S'\) に対し問題は \(i=0,1,\ldots,N-1\) に対し \(S'\) の \(i\) 文字目から \(i+M-1\) 文字目までが \(T\) と一致しているかを判定する問題となります。これは Z-algorithm で高速に計算できることが知られています。

以上を適切に実装することでこの問題に正答することができます。計算量は \(O(N+M)\) です。

実装例(Python3)

from atcoder import string

s = input()
t = input()
n, m = len(s), len(t)
a = t + "?" + s * ((m + 2 * n - 1) // n)
b = string.z_algorithm(a)
ans = 0
for i in range(n):
    if b[m + 1 + i] == m:
        ans += 1
print(ans)