# 两个字符串算法

```str1 = 'GTACCGTCA'
str2 = 'CATCGA'
def LCS_table(str1, str2):```

"""

"""

```    str_length1 = len(str1)
str_length2 = len(str2)
lcs_table = [ [0 for j in range(str_length2 + 1)] for i in range(str_length1 + 1)]
print(lcs_table)
for index1,char1 in enumerate(str1):
i = index1 + 1
for index2,char2 in enumerate(str2):
j = index2 + 1
print(i,j)
if char1 == char2:
lcs_table[i][j] = lcs_table[i-1][j-1] + 1
else:
lcs_table[i][j] = max(lcs_table[i][j-1], lcs_table[i-1][j])
return lcs_table```

"""

"""

```pattern = 'ABCDABD'
text = 'BBC ABCDAB ABCDABCDABDE'
def prefix(string):```

"""

"""

```    prefix_set = set()
length = len(string)
if length == 1:
return prefix_set
for i in range(length):
substring = string[:i]
prefix_set.remove('')
return prefix_set
def suffiex(string):```

"""

"""

```    suffiex_set = set()
length = len(string)
for i in range(length):
substring = string[i + 1:length]
suffiex_set.remove('')
return suffiex_set
def next_table(string):```

"""

"""

```    next_state_table = []
for index,char in enumerate(string):
strd = index + 1
substring = string[:strd]
p_set = prefix(substring)
s_set = suffiex(substring)
interset = p_set & s_set
if interset:
interset_number = len(max(interset))
else:
interset_number = 0
next_state_table.append(interset_number)
return next_state_table
def KMP(pattern,text):```

"""

"""

```    offset = 0#偏移位数
number = 0#模式的第几位
next_state = next_table(pattern)
for char in text:
if offset != 0:#用于跳转
offset -= 1
continue
if number == 7:#说明都匹配上了
print('success')
break
if char == pattern[number]:
number += 1
continue#这样可以一直匹配到不匹配
if char != pattern[number] and number != 0:
offset = (number) - next_state[number - 1]
number = 0```

247 篇文章32 人订阅

0 条评论

## 相关文章

3545

942

### 原生JS | 当兔子遇到鸡

HTML5学堂-码匠：当兔子遇到鸡，会怎样呢？先别急，看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样，在这个世界上，你就是独一无二的自己！ 不...

49310

### 向前字典排序

next_permutation算法对区间元素进行一次组合排序，使之字典顺序大于原来的排序，有如下两个使用原形，对迭代器区间[first,l...

2739

1332

35811

### Python内置函数int()高级用法

int()函数常用来把其他类型转换为整数，例如： >>> int(3.2) 3 >>> int(1/3) 0 其实，int是Python内置类型之一，之所以能...

3087

### Python内置函数int高级用法

int()函数常用来把其他类型转换为整数，例如： >>>int(3.2) 3 >>>int(1/3) 其实，int是Python内置类型之一，之所以能够当作函数...

2619

### 算法之旅 | 选择排序法

HTML5学堂-码匠：数据快速的计算与排序，与前端页面性能有直接的关系。由于排序的算法有很多，在本次“算法系列”的分享当中，我们先从简单易上手的选择排序法开始，...

3335

37913