Prefix based algorithms b o The search is done forward in the search window o Search for the longest prefix of the window Which is also a prefix of the pattern(s) oall the characters are read
Prefix based algorithms ⚫The search is done forward in the search window ⚫Search for the longest prefix of the window which is also a prefix of the pattern(s) ⚫all the characters are read
Suffix based algorithms o The search is done backwards along the search window Search for the longest suffix of the window which is also a suffix of the pattern(s) not all the characters are read which leads to sublinear average-case algorithms
Suffix based algorithms ⚫The search is done backwards along the search window ⚫Search for the longest suffix of the window which is also a suffix of the pattern(s) ⚫not all the characters are read, which leads to sublinear average-case algorithms
Factor based algorithms a o The search is done backwards along the search window o Search for the longest suffix of the window which is also a factor of the pattern(s) o not all the characters are read o Require to recognize the set of factors of the pattern( s)and this is quite complex
Factor based algorithms ⚫ The search is done backwards along the search window ⚫ Search for the longest suffix of the window which is also a factor of the pattern(s) ⚫ not all the characters are read ⚫ Require to recognize the set of factors of the pattern(s) and this is quite complex
Roadmap Single Multiple Prefix KMP AC_、A6 C Modified BⅣ CW(AC_BM) Suffix →SBMH BMH WM Factor BDM SBDM BOM SBOM
Roadmap
KMP ●MP: border the longest prefiⅸ v of the pattern which is also the suffix of the portion u of the text ●KMP: Longest border add“C(u+1) not equal to C(v+1)
KMP ⚫ MP: border the longest prefix v of the pattern which is also the suffix of the portion u of the text ⚫ KMP: Longest border add “C (u+1) not equal to C(v+1)