Obeta

最长公共算法相关解法

最长公共算法相关的一些解法,会不定期更新

最长公共子序列

def get_long_common_string(s1: str, s2: str):
	len1 = len(s1)
	len2 = len(s2)

	if len1 is 0 or len2 is 0:
		return 0

	if s1[0] == s2[0]:
		return get_long_common_string(s1[1:], s2[1:]) + 1

	return max(get_long_common_string(s1[1:], s2), get_long_common_string(s1, s2[1:]))


print(get_long_common_string('obeta', 'qty'))

最长公共子串

def get_long_common_sub(s1: str, s2: str):
	big_long = 0
	box = [[0] * len(s2)] * len(s1)

	for i, str1 in enumerate(s1):
		for j, str2 in enumerate(s2):
			if str1 == str2:
				if i < 1 and j < 1:
					box[i][j] = 1
					continue
				box[i][j] = box[i - 1][j - 1] + 1
				if box[i][j] > big_long:
					big_long = box[i][j]

	return big_long


print(get_long_common_sub('obeta', 'boy'))

最长相同字符子串

时间空间复杂度都为O(n).

def get_long_same_sub(s1: str):
	len_str = len(s1)

	# 长度为0时
	if len_str == 0:
		return 0

	long = 1 # 子串最短长度
	big_long = 1 # 子串最长长度

	for i, s in enumerate(s1):
		if i != len_str - 1: # 防止越界
			if s == s1[i + 1]:
				# 当前字符与下一个字符相同时加1
				long += 1
				if long > big_long:
					big_long = long
			else:
				long = 1 # 重新开始计算下一轮

	return big_long


print(get_long_same_sub('zhouyuexxxie'))

最长不重复子串

def get_long_repeat_sub(s):
	if s is '':
		return 0
	result = ''
	curr = ''

	for sub in s:
		if sub in curr:
			# 当前字符在最近的不重复字符中
			if len(curr) > len(result):
				# 记录当前最大的不重复子串
				result = curr
			curr = curr[curr.index(sub) + 1:] + sub # 核心点, 跳过遇到的重复子串,比如"ohomm"中遇到第二个"o"的时候(此时curr="oh")继续使用"h",因此curr="h" + "o", 这可以减少大量已知的文本计算
		else:
			curr += sub

	return max(
		len(result),
		len(curr), # 防止输入为 " " 的情况
	)

个人随笔记录,内容不保证完全正确,若需要转载,请注明作者和出处.