新知

最长公共子串(Longest Common Substring)

对两个字符串，找到它们的最长公共子串(Longest Common Substring)。

今天面试中把一个小妹妹坑惨了。
于是试着自己写出来。
本来想两个循环暴力找，但是觉得写不下去了。后来想了一个理解起来更简单的方法：

  1. 拿str1跟str2比较。
  2. 拿str1的最长的两个子串跟str2比较。
  3. 拿str1的次长的三个子串跟str2比较。
  4. ……

python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
str1="entertenmant"
str2="experting"

length1 = len(str1)
length2 = len(str2)
if str1 == str2:
	print("common string:" + str1)
else:
	found = False
	for del_len in range(1,length1):
		for begin_index in range(0, del_len+1):
			end_index = begin_index + (length1 - del_len)
			checkstr = str1[begin_index: end_index]
			if str2.count(checkstr) > 0:
				print("find " + checkstr + " in str2. break.")
				found = True
				break
		if found:
			break

	print("common string:" + checkstr)

不过这样的复杂度还是至少O(n^3)吧，肉眼可见的两个for循环，再加上一个count函数。
网上搜了有更普遍的方法，周末细看。