从优化到再优化最长公共子串

最长公共子串(LongestCommonSubstring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步的优化,让时间和空间复杂度一步步的减少的惊喜。最长公共子串问题的基本表述为:给定两个字符串,求出它们之间最长的相同子字符串的长度。最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同,然后取得相同最长的那个。对于一个长度为n的字符串,它有n(n+1)/2个非空子串。所以假如两个字符串的长度同为n,通过比较各个子串其算法复杂度大致为O(n4)。这还没有考虑字符