本文通过一道阿里面试题（下图），说说关于该题的字符串最长子串的查找问题。

　本文介绍 Divide and Conquer（分而治之） 的一种典型算法，FFT（快速傅里叶变换）。

DFT

DFT：$X[k] = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2 \pi k}{N} n}, k = 0, 1, 2, …, N-1$

• for each k: N complex mults, N-1 complex adds
• $e^{-j \frac{2 \pi k}{N} n}$ 预计算并保存在计算机中
• $O(N^2)$ computations for direct DFT $\Longrightarrow$ $O(N log_2 N)$ for FFT

　本周的 part 是 Divide and Conquer（分而治之）。