String Algorithms

Question 1

Finite Automata Algorithm

Answer 1

String Matching Algorithm

Question 2

Advantage of Finite Automata Algorithm

Answer 2

Matching within a single run over the text string. It traverses the text string only once.

Question 3

Why is it faster?

Answer 3

1. Due to its preprocessing.

2. Types of string it matches. (unlike Aho Corasick)

Question 4

Likely concept

Answer 4

Deterministic Finite Automata (DFA) in TOC.

Question 5

Processes it goes through

Answer 5

Following is the set of processes :

1. Construction of Finite Automata Machine for the pattern string.
2. Once the preprocessing is completed text string will be passed through this automata and in the sequential order, it matches the states as well.
3. The decision of being matched or not depending upon the current state after text string is finished.

Question 6

Number of states in FA

Answer 6

Length of pattern + 1 (M + 1)

Question 7

How to construct the Finite Automata for the pattern.

Answer 7

It is constructed using the concept of the borders just as like in the KMP algorithm. The KMP algorithm utilizes the concept of borders in order to use the mismatches for the matching with a prefix so that mismatch may do lesser harm to the overall matching procedure.

Question 8

Describe the key point about process

Answer 8

The main point about the calculation of the finite automata states and their jumping from one to the other is done using the longest length borders that is available at the moment for the matching. As it matches the longest length returns the endpoint of the prefix to jump on.