Optimization

最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值，所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已，关键还是享受把学习算法一步步的优化，让时间和空间复杂度一步步的减少的惊喜。

概览

最长公共子串问题的基本表述为：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串，而只要考虑每个子串的开始位置就可以，这样可以把复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法，在后边会更加详细介绍这个问题使用动态规划法的契机：有重叠的子问题。进而可以通过空间换时间，让复杂度优化到O(n2)，代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲，对于最长公共子串问题，O(n2)已经是目前我所知最优的了，也是面试时所期望达到的。但是对于空间复杂度O(n2)并不算什么，毕竟算法上时间比空间更重要，但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一步的可以把空间复杂度减少到O(n)，这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回原来的O(1)，而时间上如果幸运还可以等于O(n)。
Read More →