COURSEWORK 1 FOR INF2B (ADS THREAD, 2018-19) STRING MATCHING
- 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
- Practice at asymptotic analysis (with guidance).
- Careful implementation of one algorithm (an implementation of the other algorithm is supplied).
- 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.
4.实现过程：[部分核⼼代码截图, 截图部分的代码prefer 中英⽂注 释]
1. KMP 匹配算法核⼼
7.学习建议：[根据学习IT的经验，写1-3点, prefer 3个点]
2. 了解 KMP 匹配算法的原理