Exact String Matching Problem.ppt

10/17/2001 Algorithms for Bioinformatics Exact String Matching Problem ? INPUT: P and T ? OUTPUT: all occurrences of P in T ? TIME: O(|P|+|T|) ? TRICK: Fundamental Preprocessing (Pattern and Text) (Pattern and Text) (linear time) (linear time) PT Z Z[|P|+i]>=|P| ? P occurs in T[i .. i+|P|-1] 10/17/2001 Algorithms for Bioinformatics Exact String Matching Problem ? Q1 : Can we solve the problem in O(|T|) time if we know P in advance? ? Q2 : Can we solve the problem in O(|P|) time if we know T in advance? ? By Fundamental Preprocessing? ? By any algorithm? 10/17/2001 Algorithms for Bioinformatics Suffix Trees Input: P, T Output: ? an occurrence of P in T, if any ?“ NO ” if P does not occur in T EXECT STRING MATCHING SUB STRING PROBLEM 10/17/2001 Algorithms for Bioinformatics Suffix Trees ? Chapter 5: Introduction ? Chapter 6: Construction Algorithms ? Chapter 7: Aplications ? Chapter 8: mon Ancestor ? Chapter 9: More Applicaitons 10/17/2001 Algorithms for Bioinformatics Substring Matching ? String S: bbabbaab (|S|=m) ? Pattern P: baa (|P|=n) ? Objective: 在S中找 P ? Techniques: ? Preprocessing P O(n) time ? Boyer-Moore O(m ) time ? Knuth- Merris - Prott O(m ) time – Preprocessing S O(m) time ? Suffix-tree-matching O(n) time!! 10/17/2001 Algorithms for Bioinformatics Suffixes 與 String Matching S= bbabbaab 1 st suffix = bbabbaab 2 nd suffix = babbaab 3 rd suffi