N=∣S∣,M=∣T∣N = |S|, M = |T|N=∣S∣,M=∣T∣とします。 N,MN, MN,Mは十分に小さいので、i=1,2,...,N−Mi = 1, 2, ..., N-Mi=1,2,...,N−Mについて、SSSのiii文字目からi+M−1i+M-1i+M−1文字目までの文字列がTTTと一致するかを愚直に判定しても十分に間に合います。
おまけ: 同様に1≤N,M≤1051 \leq N, M \leq 10 ^ 51≤N,M≤105の制約でも解けますか？
