HCMUT - CO3031 - Algorithm Analysis and Design

This repository contain source code for the course project

Project

Propose and implement an algorithm to solve pattern matching problem. Analyse algorithm complexity.

Input

• A long paragraph
• Several patterns to search for

Output

• For each pattern, if exist in paragraph, print out all its occurrences

Solution

• Construct a suffix array from given paragraph
• Use binary search algorithm to find the pattern

Complexity

• Initialization: O(N^2 * logN)
  • String compare: O(N)
  • Quicksort: O(NlogN)
• Searching: O(M * logN * P)
  • String compare: O(M)
  • Binary search: O(logN)

With

• N is the length of the paragraph
• M is the length of the pattern
• P is the number of patterns

Reference

https://cp-algorithms.com/string/suffix-array.html#finding-a-substring-in-a-string