Exact String Matching

Caution

This is not finished page

Reading

	Online	Offline
Exact	✅	❓
Approximate	❓	❓

Exact online string matching is covered in depth in:

• Exact Online String Matching Bibliography
• Exact string matching algorithms
• The String Matching Algorithms Research Tool
• The Exact Online String Matching Problem:a Review of the Most Recent Results
• Exact String Matching Algorithms: Survey, Issues, and Future Research Directions
• Technology Beats Algorithms (in Exact String Matching)

Approximate online string matching:

• A guided tour to approximate string matching

Approximate offline string matching:

• Offline Approximate String Matching for Information Retrieval: An experiment on technical documentation

Graphs

Dependency on the size of the alphabet and length of strings

Gonzalo Navarro & Mathieu Raffinot, 2002:

Exact online string matching bibliography

See Chronology of Exact Online String Matching Algorithms

Algorithms classification

1. Type
   • Exact
     • Substring
     • Pattern
   • Approximate
2. For approximate matching
   • Type of measure (edit distance/similarity)
   • Ranking function
   • Recall and precision
3. Based on
   • characters comparison
   • automata
   • bit-parallelism
   • packed string matching
   • …
4. Depends on size of
   • alphabet
   • text
   • query
5. Relationship to other algorithms
   • Combination of / Modification of / Refinement of / Variant of / Improvement of / Simplification of

WIP

Approximate String Matching using Backtracking over Suffix Arrays:

	Online	Offline
Exact	KMP O(n+m)	Suffix Tree O(m)
Approximate	Dynamic Programming O(n·m), Landau+Vishkin O(k·n)	Myers, Navarro+Baeza-Yates, Ukkonnen