AskSia

Plus

Answer questions and provide explanations Question 2 (14 marks) 1. Given a patte...

May 11, 2024

Answer questions and provide explanations

python

Explanation

The create_shift_table function initializes a table with the length of the pattern for each character and then updates it with the rightmost occurrence of each character in the pattern. The horspool_search function uses this table to find the pattern in the text and count the number of comparisons.

Step-by-step Instruction

▪

Initialize the table with the length of the pattern for each character

▪

Update the table with the rightmost occurrence of each character in the pattern

▪

Define the horspool_search function to apply Horspool's algorithm for pattern searching

▪

Create the shift table for the given pattern within the horspool_search function

▪

Initialize the number of comparisons and the index of the text where the pattern is aligned

▪

Use a while loop to go through the text and match the pattern from the end

▪

If the pattern is found, return the number of comparisons

▪

If the pattern is not found, shift the pattern according to the shift table and increment the number of comparisons

▪

Define the main function to test the create_shift_table and horspool_search functions with use cases

▪

Call the main function to run the tests

Time Complexity

The time complexity of Horspool's algorithm is O(n) in the best case and O(nm) in the worst case, where n is the length of the text and m is the length of the pattern.

Space Complexity

The space complexity is O(1) since the shift table size is constant and does not depend on the size of the text or the pattern.

Provide the above Chinese explanation

对于问题1，创建一个移位表，用于Horspool算法中的模式CGTGC。对于字母A，G，C，T的移位表如下：

▪

A: 移位值为5，因为A没有在模式中出现，所以移位值为模式的长度。

▪

G: 移位值为2，因为G在模式中从右边数是第二个字符。

▪

C: 移位值为1，因为C在模式中从右边数是最后一个字符。

▪

T: 移位值为3，因为T在模式中从右边数是第三个字符。

对于问题2，使用Horspool算法在文本AGCCGTGC中搜索模式CGTGC，比较的次数如下：

▪

第一步：将模式与文本的最右端对齐，比较模式的最后一个字符C与文本中的C，匹配成功，继续比较前一个字符。

▪

第二步：比较模式中的T与文本中的G，不匹配。根据移位表，G的移位值为2，因此模式向右移动2位。

▪

第三步：将模式向右移动2位后，再次比较模式的最后一个字符C与文本中的C，匹配成功，继续比较前一个字符。

▪

第四步：比较模式中的T与文本中的T，匹配成功，继续比较前一个字符。

▪

第五步：比较模式中的G与文本中的G，匹配成功，继续比较前一个字符。

▪

第六步：比较模式中的C与文本中的C，匹配成功，继续比较前一个字符。

▪

第七步：比较模式中的G与文本中的A，不匹配。根据移位表，A的移位值为5，因此模式向右移动5位。

▪

第八步：模式已经移动到文本的末尾，搜索结束。

▪

总共进行了7次比较。