本文主要参考http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html的讲解，本人自己用python实现了一下暴力法，动态规划。
# coding: utf-8 # ## 最长公共子串问题 # # ### 暴力法求解 VS 动态规划 # # ### 参考自http://www.cnblogs.com/ider/p/longest-common-substring-problem-optimization.html # # ## 方法一：暴力法求解 # ### 时间复杂度（o^3）,空间复杂度（1） # In[2]: get_ipython().magic('pdb on') # In[1]: import numpy as np # In[18]: # 获取字符串str1和str2最长公共子串的长度与起始位置 def getLongestSubstring(str1,str2): longest=0 start_pos1=-1 start_pos2=-1 compares=0 # 记录比较次数 for i in range(len(str1)): for j in range(len(str2)): length=0 m=i n=j while str1[m]==str2[n]: compares+=1 length+=1 m+=1 n+=1 if (m>=len(str1))|(n>=len(str2)): break if longest<length: compares+=1 longest=length start_pos1=i start_pos2=j return longest,start_pos1,start_pos2,compares # ## 方法二：动态规划 # ### 未优化时，时间复杂度（o^2），空间复杂度（o^2） # In[17]: # 通过动态规划的方法优化求解最长公共子串 def getLongestSubstring_dp(str1,str2): str1_len=len(str1) str2_len=len(str2) compares=0 if (str1_len==0)|(str2_len)==0: return -1 # 定义一个二维数据记录最长子串长度 m=np.zeros([str1_len,str2_len],dtype=np.int) for j in range(str2_len): compares+=1 m[0][j]=1 if str1[0]==str2[j] else 0 for i in range(1,str1_len): compares+=1 m[i][0]=1 if str1[i]==str2[0] else 0 for j in range(1,str2_len): compares+=1 m[i][j]=m[i-1][j-1]+1 if str1[i]==str2[j] else 0 # 寻找矩阵中最大的数，也就是最长公共子串的长度 longest=0 start_pos1=-1 start_pos2=-1 for i in range(str1_len): for j in range(str2_len): if longest<m[i][j]: longest=m[i][j] start_pos1=i-longest+1 start_pos2=j-longest+1 return longest,start_pos1,start_pos2,compares # ### 优化后，时间复杂度（o^2）,空间复杂度（n） # In[16]: def getLongestSubstring_dp2(str1,str2): str1_len=len(str1) str2_len=len(str2) if (str1_len==0)|(str2_len==0): return -1 start_pos1=0 start_pos2=0 longest=0 compares=0 m=np.zeros([2,str2_len],dtype=np.int) # 只用两行就可以计算最长子串长度 for j in range(str2_len): if str1[0]==str2[j]: compares+=1 m[0][j]=1 if longest==0: longest=1 start_pos1=0 start_pos2=j for i in range(1,str1_len): # 通过且运算计算出当前行和先前行 cur=int((i&1)==1) pre=int((i&1)==0) if str1[i]==str2[0]: compares+=1 m[cur][0]=1 if longest==0: longest=1 start_pos1=i start_pos2=0 for j in range(1,str2_len): if str1[i]==str2[j]: compares+=1 m[cur][j]=m[pre][j-1]+1 if longest<m[cur][j]: longest=m[cur][j] start_pos1=i-longest+1 start_pos2=j-longest+1 return longest,start_pos1,start_pos2,compares # ## 测试 # In[19]: str1='abcababdcababc' str2='ababc' length,s1,s2,com=getLongestSubstring(str1,str2) print(length,s1,s2,com) length,s1,s2,com=getLongestSubstring_dp(str1,str2) print(length,s1,s2,com) length_3,s1_3,s2_3,com_3=getLongestSubstring_dp2(str1,str2) print(length,s1,s2,com)