作业辅导-java实现KMP匹配算法

作业辅导-java实现KMP匹配算法

, ,

作业辅导解析‌

COURSEWORK 1 FOR INF2B (ADS THREAD, 2018-19) STRING MATCHING

[作业标题]

16th Feb,2019[⽇期]

1.作业题⽬目：[Assignment上⾯随便复制⼀点]

  • In this practical we will consider two methods of searching for all occurrences of a given pattern within some text (both given as strings). For example we might have a long piece of English text about Scotland and we wish to search for all occurrences of “Edinburgh” within it. Our aim is to return the offset position of all occurrences, if there are no occurrences then we indicate this by a
special convention discussed below.

2.作业⽬目的：[作业的⽬的1-3个点都可以]

  1. Practice at asymptotic analysis (with guidance).
  2. Careful implementation of one algorithm (an implementation of the other algorithm is supplied).
  3. Carry out timing experiments in order to:
    • (a) Compare the algorithm that you implement with one that is supplied and decide the point from which one is more efficient than the other (i.e., the overheads are over- weighed by the advantages).
    • (b) Determine the constant for the asymptotic analysis as it applies to your particular implementation.

3.运⾏行行效果： [运⾏结果截图]

4.实现过程：[部分核⼼代码截图, 截图部分的代码prefer 中英⽂注 释]

image

参考源码图 1.1

核⼼代码上图所⽰，本次作业主要通过以下步骤实现：

1. KMP 匹配算法核⼼

5.知识点巩固：[相关知识点1-3点总结]

–数组

KMP 字符串查找匹配算法

6.知识拓拓展：[拓展知识点1-3点总结]

– 数组

– 时间复杂度

– 字符串串匹配

– KMP

7.学习建议：[根据学习IT的经验，写1-3点, prefer 3个点]

1.了解时间复杂度，空间复杂度等基本概念。

2. 了解 KMP 匹配算法的原理