中图收术大 算法基础 第八讲:串匹配算法 主讲:顾乃杰教授 单位:计算机科学技术学院 方創 天寰 学期:2016-2017(秋) 基下宇 港英 题才 學府一
算法基础 第八讲：串匹配算法 主 讲: 顾 乃 杰 教授 单 位: 计算机科学技术学院 学 期: 2016-2017 (秋)
SIVERSITY ScIE\CE TECH\OLoGY 主要内容 CHINA The Naive algorithm(Brute Force The Knuth-Morris-Pratt Algorithm ◆ The ShIFt-Or algorithm The boyer-Moore algorithm The boyer-Moore-Horspool algorithm The Karp-Rabin algorithm C onclusion 本教案参考了下述有关 String Searching Algorithm的教案,在此表示感谢: 1.中国台湾省国立中山大学黄三益教授的教案 2. Princeton University· Kevin Wayne· Theory of algorithms·COS42 021/2 &T
2021/2/4 Department of Computer Science & Technology 2 主要内容 ◆ The Naive Algorithm (Brute Force ) ◆ The Knuth-Morris-Pratt Algorithm ◆ The SHIFT-OR Algorithm ◆ The Boyer-Moore Algorithm ◆ The Boyer-Moore-Horspool Algorithm ◆ The Karp-Rabin Algorithm ◆ Conclusion 本教案参考了下述有关 String Searching Algorithm 的教案，在此表示感谢： 1. 中国台湾省 国立中山大学 黃三益教授的教案 2. Princeton University • Kevin Wayne • Theory of Algorithms • COS 42
SIVERSITY ScIE\CE TECH\OLoGY 8.0串匹配问题 CHINA a String-matching Problem 1. Find one occurrences of a pattern in a text 2. Find out all the occurrences of a pattern in a text a Applications require two kinds of solution depending on which string, the pattern or the text, is given first algorithms based on the use of automata or combinatorial properties of strings are commonly implemented to preprocess the pattern and sol ve the first kind of problem 2. The notion of indexes realized by trees or automata is used in the second kind of solutions 021/2 &T
2021/2/4 Department of Computer Science & Technology 3 8.0 串匹配问题 String-matching Problem: 1. Find one occurrences of a pattern in a text ; 2. Find out all the occurrences of a pattern in a text. Applications require two kinds of solution depending on which string, the pattern or the text, is given first. 1. Algorithms based on the use of automata or combinatorial properties of strings are commonly implemented to preprocess the pattern and solve the first kind of problem. 2. The notion of indexes realized by trees or automata is used in the second kind of solutions
SIVERSITY ScIE\CE TECH\OLoGY 串匹配及其应用 CHINA 口 Some applications Wo word processors Virus scanning Text information retrieval systems. Lexis, Nexis) Digital libraries Natural language processing Specialized databases Computational molecular biology Web eb search engines Bioinformatic 021/2 &T
2021/2/4 Department of Computer Science & Technology 4 串匹配及其应用 Some applications. ➢ Word processors. ➢ Virus scanning. ➢ Text information retrieval systems. (Lexis, Nexis) ➢ Digital libraries. ➢ Natural language processing. ➢ Specialized databases. ➢ Computational molecular biology. ➢ Web search engines. ➢ Bioinformatic
SIVERSITY ScIE\CE TECH\OLoGY 串匹配示例 CHINA Search Text n nee edeneenee dl e n l d Search Pattern needle Successful Search n nee nledeneeneed len l d Search Pattern ne e dle 021/2 &T
2021/2/4 Department of Computer Science & Technology 5 串匹配示例 n n e e n l Search Text e d e n e e n e e d l e n l d n e e d l e Search Pattern Successful Search n n e e n l e d e n e e n e e d l e n l d n e e d l e Search Pattern