Fast Fourier Transform, Algorithms, Pattern Matching, Convolution, Combination Sum.
when M = O(N). If say M=O(N²) then the FFT based approach has time complexity of O(N²logN) which is greater than O(N²). Let’s look at a slightly different problem. Pattern Search In String Given a string S of length N, consisting of lowercase english alphabets a-z and a pattern T of length M, again