# Introduction To

Pattern Searching Algorithms

Pattern Searching algorithms are used to find a pattern or substring from another bigger string. There are different algorithms. The main goal to design these type of algorithms to reduce the time complexity. The traditional approach may take lots of time to complete the pattern searching task for a longer text.

Here we will see different algorithms to get a better performance of pattern matching.

# Course Structure

## Algorithms

- Naive algorithm for Pattern Searching
- KMP Algorithm for Pattern Searching
- Rabin-Karp Algorithm for Pattern Searching
- Optimized Naive Algorithm for Pattern Searching
- Finite Automata algorithm for Pattern Searching
- Pattern Searching | Set 6 (Efficient Construction of Finite Automata)
- Boyer Moore Algorithm for Pattern Searching
- Boyer Moore Algorithm | Good Suffix heuristic
- Aho-Corasick Algorithm for Pattern Searching
- Suffix Array | Set 1 (Introduction)
- kasai’s Algorithm for Construction of LCP array from Suffix Array
- Z algorithm (Linear time pattern searching Algorithm)
- Online algorithm for checking palindrome in a stream
- Manacher’s Algorithm – Linear Time Longest Palindromic Substring – Part 4
- Ukkonen’s Suffix Tree Construction – Part 1
- Ukkonen’s Suffix Tree Construction – Part 2
- Ukkonen’s Suffix Tree Construction – Part 3
- Ukkonen’s Suffix Tree Construction – Part 4
- Ukkonen’s Suffix Tree Construction – Part 5
- Ukkonen’s Suffix Tree Construction – Part 6
- Generalized Suffix Tree 1

## Questions

- Anagram Substring Search (Or Search for all permutations)
- Pattern Searching using a Trie of all Suffixes
- Program to wish Women’s Day
- Program to replace a word with asterisks in a sentence
- Dynamic Programming | Wildcard Pattern Matching | Linear Time and Constant Space
- Pattern Searching using C++ library
- Longest prefix which is also suffix
- Splitting a Numeric String
- Count of number of given string in 2D character array
- Find minimum shift for longest common prefix
- Find all the patterns of “1(0+)1” in a given string | SET 1(General Approach)
- Find all the patterns of “1(0+)1” in a given string | SET 2(Regular Expression Approach)
- is_permutation() in C++ and its application for anagram search
- Match Expression where a single special character in pattern can match one or more characters
- Maximum length prefix of one string that occurs as subsequence in another
- Wildcard Pattern Matching
- Find all occurrences of a given word in a matrix
- Search a Word in a 2D Grid of characters
- String matching where one string contains wildcard characters
- Suffix Tree Application 1 – Substring Check
- Suffix Tree Application 2 – Searching All Patterns
- Suffix Tree Application 3 – Longest Repeated Substring
- Suffix Tree Application 4 – Build Linear Time Suffix Array
- Suffix Tree Application 5 – Longest Common Substring
- Suffix Tree Application 6 – Longest Palindromic Substring