# Python 数据结构和算法实用指南（四）（1）

## 第十二章：字符串算法和技术

• 学习 Python 中字符串的基本概念
• 学习模式匹配算法及其实现
• 理解和实现 Rabin-Karp 模式匹配算法
• 理解和实现 Knuth-Morris-Pratt（KMP）算法
• 理解和实现 Boyer-Moore 模式匹配算法

## 字符串符号和概念

string =  "this is data structures book by packt publisher"; suffix =  "publisher"; prefix = "this"; print(string.endswith(suffix))  #Check if string contains given suffix.
print(string.startswith(prefix)) #Check if string starts with given prefix.
#Outputs
>>True
>>True

## 暴力算法

def brute_force(text, pattern):
l1 = len(text)      # The length of the text string
l2 = len(pattern)   # The length of the pattern
i = 0
j = 0               # looping variables are set to 0
flag = False        # If the pattern doesn't appear at all, then set this to false and execute the last if statement
while i < l1:         # iterating from the 0th index of text
j = 0
count = 0
# Count stores the length upto which the pattern and the text have matched
while j < l2:
if i+j < l1 and text[i+j] == pattern[j]:
# statement to check if a match has occoured or not
count += 1     # Count is incremented if a character is matched
j += 1
if count == l2:   # it shows a matching of pattern in the text
print("\nPattern occours at index", i)
# print the starting index of the successful match
flag = True
# flag is True as we wish to continue looking for more matching of
pattern in the text.
i += 1
if not flag:
# If the pattern doesn't occours at all, means no match of
pattern in the text string
print('\nPattern is not at all present in the array')
brute_force('acbcabccababcaacbcac','acbcac')         # function call
#outputs
#Pattern occours at index 14

if i+j<l1 and text[i+j] == pattern[j]:

## 拉宾-卡普算法

1. 首先，在开始搜索之前，我们对模式进行预处理，即计算长度为m的模式的哈希值以及长度为m的文本的所有可能子字符串的哈希值。因此，可能的子字符串的总数将是(n-m+1)。这里，n是文本的长度。
2. 我们比较模式的哈希值，并逐一与文本的子字符串的哈希值进行比较。
3. 如果哈希值不匹配，我们就将模式向前移动一位。
4. 如果模式的哈希值和文本的子字符串的哈希值匹配，那么我们逐个比较模式和子字符串的字符，以确保模式实际上在文本中找到。
5. 我们继续进行步骤 2-4 的过程，直到达到给定文本字符串的末尾。

## 实现 Rabin-Karp 算法

def generate_hash(text, pattern):
ord_text = [ord(i) for i in text]
# stores unicode value of each character in text
ord_pattern = [ord(j) for j in pattern]
# stores unicode value of each character in pattern
len_text = len(text)           # stores length of the text
len_pattern = len(pattern)     # stores length of the pattern
hash_pattern = sum(ord_pattern)
len_hash_array = len_text - len_pattern + 1
#stores the length of new array that will contain the hash
values of text
hash_text = [0]*(len_hash_array)
# Initialize all the values in the array to 0.
for i in range(0, len_hash_array):
if i == 0:
hash_text[i] = sum(ord_text[:len_pattern])
# initial value of hash function
else:
hash_text[i] = ((hash_text[i-1] - ord_text[i-1]) +
ord_text[i+len_pattern-1])
# calculating next hash value using previous value
return [hash_text, hash_pattern]         # return the hash values

Rabin-Karp 算法的完整 Python 实现如下所示：

def Rabin_Karp_Matcher(text, pattern):
text = str(text)                 # convert text into string format
pattern = str(pattern)           # convert pattern into string format
hash_text, hash_pattern = generate_hash(text, pattern)
# generate hash values using generate_hash function
len_text = len(text)              # length of text
len_pattern = len(pattern)        # length of pattern
flag = False # checks if pattern is present atleast once or not at all
for i in range(len(hash_text)):
if hash_text[i] == hash_pattern:     # if the hash value matches
count = 0
for j in range(len_pattern):
if pattern[j] == text[i+j]:
# comparing patten and substring character by character
count += 1
else:
break
if count == len_pattern:       # Pattern is found in the text
flag = True                # update flag accordingly
print("Pattern occours at index", i)
if not flag:                # Pattern doesn't match even once.
print("Pattern is not at all present in the text")

Rabin-Karp 模式匹配算法在搜索之前预处理模式，即计算模式的哈希值，其复杂度为O(m)。此外，Rabin-Karp 算法的最坏情况运行时间复杂度为O(m *(n-m+1))

## Knuth-Morris-Pratt 算法

Knuth-Morris-PrattKMP）算法是一种基于预先计算的前缀函数的模式匹配算法，该函数存储了模式中重叠文本部分的信息。KMP 算法预处理这个模式，以避免在使用前缀函数时进行不必要的比较。该算法利用前缀函数来估计模式应该移动多少来搜索文本字符串中的模式，每当我们得到一个不匹配时。KMP 算法是高效的，因为它最小化了给定模式与文本字符串的比较。

KMP 算法背后的动机可以在以下解释性图表中看到：

## 前缀函数

prefix函数（也称为失败函数）在模式中查找模式本身。当出现不匹配时，它试图找出由于模式本身的重复而可以重复使用多少之前的比较。它的值主要是最长的前缀，也是后缀。

prefix函数的值显示了如果不匹配，字符串的开头有多少可以重复使用。例如，如果在索引位置5处比较失败，prefix函数的值为2，这意味着不需要比较前两个字符。

## 理解 KMP 算法

KMP 模式匹配算法使用具有模式本身重叠的模式，以避免不必要的比较。KMP 算法的主要思想是根据模式中的重叠来检测模式应该移动多少。算法的工作原理如下：

1. 首先，我们为给定的模式预先计算prefix函数，并初始化一个表示匹配字符数的计数器 q。
2. 我们从比较模式的第一个字符与文本字符串的第一个字符开始，如果匹配，则递增模式的计数器q和文本字符串的计数器，并比较下一个字符。
3. 如果不匹配，我们将预先计算的prefix函数的值赋给q的索引值。
4. 我们继续在文本字符串中搜索模式，直到达到文本的末尾，即如果我们找不到任何匹配。如果模式中的所有字符都在文本字符串中匹配，我们返回模式在文本中匹配的位置，并继续搜索另一个匹配。

KMP 算法有两个阶段，预处理阶段，这是我们计算“前缀”函数的地方，它的空间和时间复杂度为O(m)，然后，在第二阶段，即搜索阶段，KMP 算法的时间复杂度为O(n)

## 实现 KMP 算法

k 的值是由“前缀”函数计算得出的值，因此我们将其分配给模式的q的索引位置。最后，我们返回具有模式每个字符的计算值的“前缀”函数列表。以下是“前缀”函数的代码：

def pfun(pattern): # function to generate prefix function for the given pattern
n = len(pattern) # length of the pattern
prefix_fun = [0]*(n) # initialize all elements of the list to 0
k = 0
for q in range(2,n):
while k>0 and pattern[k+1] != pattern[q]:
k = prefix_fun[k]
if pattern[k+1] == pattern[q]: # If the kth element of the pattern is equal to the qth element
k += 1            # update k accordingly
prefix_fun[q] = k
return prefix_fun         # return the prefix function 

def KMP_Matcher(text,pattern):
m = len(text)
n = len(pattern)
flag = False
text = '-' + text       # append dummy character to make it 1-based indexing
pattern = '-' + pattern       # append dummy character to the pattern also
prefix_fun = pfun(pattern) # generate prefix function for the pattern
q = 0
for i in range(1,m+1):
while q>0 and pattern[q+1] != text[i]:
# while pattern and text are not equal, decrement the value of q if it is > 0
q = prefix_fun[q]
if pattern[q+1] == text[i]: # if pattern and text are equal, update value of q
q += 1
if q == n: # if q is equal to the length of the pattern, it means that the pattern has been found.
print("Pattern occours with shift",i-n) # print the index,
where first match occours.
flag = True
q = prefix_fun[q]
if not flag:
print('\nNo match found')
KMP_Matcher('aabaacaadaabaaba','abaac')         #function call

## Boyer-Moore 算法

Boyer-Moore 模式匹配算法是另一种这样的算法（除了 KMP 算法），它通过使用一些方法跳过一些比较来进一步提高模式匹配的性能。您需要理解以下概念才能使用 Boyer-Moore 算法：

1. 在这个算法中，我们将模式从左向右移动，类似于 KMP 算法
2. 我们从右向左比较模式和文本字符串的字符，这与 KMP 算法相反
3. 该算法通过使用好后缀和坏字符移位的概念来跳过不必要的比较

## 理解 Boyer-Moore 算法

Boyer-Moore 算法从右到左比较文本上的模式。它通过预处理模式来使用模式中各种可能的对齐信息。这个算法的主要思想是我们将模式的末尾字符与文本进行比较。如果它们不匹配，那么模式可以继续移动。如果末尾的字符不匹配，就没有必要进行进一步的比较。此外，在这个算法中，我们还可以看到模式的哪一部分已经匹配（与匹配的后缀），因此我们利用这个信息，通过跳过任何不必要的比较来对齐文本和模式。

• 坏字符启发式
• 好后缀启发式

## 坏字符启发式

Boyer-Moore 算法将模式和文本字符串从右到左进行比较。它使用坏字符启发式来移动模式。根据坏字符移位的概念，如果模式的字符与文本不匹配，那么我们检查文本的不匹配字符是否出现在模式中。如果这个不匹配的字符（也称为坏字符）不出现在模式中，那么模式将被移动到这个字符的旁边，如果该字符在模式中的某处出现，我们将模式移动到与文本字符串的坏字符对齐的位置。

Python 数据结构和算法实用指南（四）（2）https://developer.aliyun.com/article/1507641

|
2天前
|

【Python核心数据结构探秘】：元组与字典的完美协奏曲
【Python核心数据结构探秘】：元组与字典的完美协奏曲
11 0
|
3天前
|

【数据结构与算法】：手搓顺序表（Python篇）
【数据结构与算法】：手搓顺序表（Python篇）
8 1
|
3天前
|

Python零基础入门-5 数据结构（集合和字典）
Python零基础入门-5 数据结构（集合和字典）
7 1
|
3天前
|

Python零基础入门-5 数据结构（列表和元组
Python零基础入门-5 数据结构（列表和元组
8 1
|
3天前
|

10 3
|
3天前
|

12 2
|
3天前
|

13 1
|
4天前
|

13 2
|
3天前

7 1
|
6天前
|

12 3