Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
index U in S, check if T equals the substring S[U:U+M]. Time complexity is O(NM) because we are sliding over S of size N and each window is of size M. The best algorithm known for this problem is the KMP (Knuth-Morris-Pratt) algorithm which solves the problem in O(N+M) time complexity. But we will