For example, let us see how to get the next state from current state 5 and character ‘C’ in the above diagram. The value of length gives us the next state.
The idea is to get length of the longest prefix of the given pattern such that the prefix is also suffix of “patx”. Given a character x and a state k, we can get the next state by considering the string “patx” which is basically concatenation of pattern characters pat, pat … pat and the character x. The main thing to construct FA is to get the next state from the current state for every possible character. Number of states in FA will be M+1 where M is length of the pattern. The above diagrams represent graphical and tabular representations of pattern ACACAGA. The time complexity of the search process is O(n).īefore we discuss FA construction, let us take a look at the following FA for pattern ACACAGA. If we reach the final state, then the pattern is found in the text. At every step, we consider next character of text, look for the next state in the built FA and move to a new state. In search, we simply need to start from the first state of the automata and the first character of the text. Once the FA is built, the searching is simple. Construction of the FA is the main tricky part of this algorithm. In FA based algorithm, we preprocess the pattern and build a 2D array that represents a Finite Automata. In this post, we will discuss Finite Automata (FA) based pattern searching algorithm. We have discussed the following algorithms in the previous posts: When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results. Pattern searching is an important problem in computer science. You may assume that n > m.Įxamples: Input: txt = "THIS IS A TEST TEXT" Given a text txt and a pattern pat, write a function search(char pat, char txt) that prints all occurrences of pat in txt.