In the previous post, we discussed Finite Automata based pattern searching algorithm. The FA (Finite Automata) construction method discussed in previous post takes O((m^3)*NO_OF_CHARS) time. FA can be constructed in O(m*NO_OF_CHARS) time. In this post, we will discuss the O(m*NO_OF_CHARS) algorithm for FA construction. The idea is similar to lps (longest prefix suffix) array construction discussed in the KMP algorithm. We use previously filled rows to fill a new row.

C-C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata

C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata

The abvoe diagrams represent graphical and tabular representations of pattern ACACAGA.

Algorithm:
1) Fill the first row. All entries in first row are always 0 except the entry for pat[0] character. For pat[0] character, we always need to go to state 1.
2) Initialize lps as 0. lps for the first index is always 0.
3) Do following for rows at index i = 1 to M. (M is the length of the pattern)
…..a) Copy the entries from the row at index equal to lps.
…..b) Update the entry for pat[i] character to i+1.
…..c) Update lps “lps = TF[lps][pat[i]]” where TF is the 2D array which is being constructed.

[ad type=”banner”]

Implementation
Following is C implementation for the above algorithm.

[pastacode lang=”c” manual=”%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%23define%20NO_OF_CHARS%20256%0A%20%0A%2F*%20This%20function%20builds%20the%20TF%20table%20which%20represents%20Finite%20Automata%20for%20a%0A%20%20%20given%20pattern%20%20*%2F%0Avoid%20computeTransFun(char%20*pat%2C%20int%20M%2C%20int%20TF%5B%5D%5BNO_OF_CHARS%5D)%0A%7B%0A%20%20%20%20int%20i%2C%20lps%20%3D%200%2C%20x%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20entries%20in%20first%20row%0A%20%20%20%20for%20(x%20%3D0%3B%20x%20%3C%20NO_OF_CHARS%3B%20x%2B%2B)%0A%20%20%20%20%20%20%20TF%5B0%5D%5Bx%5D%20%3D%200%3B%0A%20%20%20%20TF%5B0%5D%5Bpat%5B0%5D%5D%20%3D%201%3B%0A%20%0A%20%20%20%20%2F%2F%20Fill%20entries%20in%20other%20rows%0A%20%20%20%20for%20(i%20%3D%201%3B%20i%3C%3D%20M%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%2F%2F%20Copy%20values%20from%20row%20at%20index%20lps%0A%20%20%20%20%20%20%20%20for%20(x%20%3D%200%3B%20x%20%3C%20NO_OF_CHARS%3B%20x%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20TF%5Bi%5D%5Bx%5D%20%3D%20TF%5Blps%5D%5Bx%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20the%20entry%20corresponding%20to%20this%20character%0A%20%20%20%20%20%20%20%20TF%5Bi%5D%5Bpat%5Bi%5D%5D%20%3D%20i%20%2B%201%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Update%20lps%20for%20next%20row%20to%20be%20filled%0A%20%20%20%20%20%20%20%20if%20(i%20%3C%20M)%0A%20%20%20%20%20%20%20%20%20%20lps%20%3D%20TF%5Blps%5D%5Bpat%5Bi%5D%5D%3B%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Prints%20all%20occurrences%20of%20pat%20in%20txt%20*%2F%0Avoid%20search(char%20*pat%2C%20char%20*txt)%0A%7B%0A%20%20%20%20int%20M%20%3D%20strlen(pat)%3B%0A%20%20%20%20int%20N%20%3D%20strlen(txt)%3B%0A%20%0A%20%20%20%20int%20TF%5BM%2B1%5D%5BNO_OF_CHARS%5D%3B%0A%20%0A%20%20%20%20computeTransFun(pat%2C%20M%2C%20TF)%3B%0A%20%0A%20%20%20%20%2F%2F%20process%20text%20over%20FA.%0A%20%20%20%20int%20i%2C%20j%3D0%3B%0A%20%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20N%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20j%20%3D%20TF%5Bj%5D%5Btxt%5Bi%5D%5D%3B%0A%20%20%20%20%20%20%20if%20(j%20%3D%3D%20M)%0A%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20printf%20(%22%5Cn%20pattern%20found%20at%20index%20%25d%22%2C%20i-M%2B1)%3B%0A%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20%20char%20*txt%20%3D%20%22GEEKS%20FOR%20GEEKS%22%3B%0A%20%20%20%20char%20*pat%20%3D%20%22GEEKS%22%3B%0A%20%20%20%20search(pat%2C%20txt)%3B%0A%20%20%20%20getchar()%3B%0A%20%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/]

Output:

 pattern found at index 0
 pattern found at index 10

Time Complexity for FA construction is O(M*NO_OF_CHARS). The code for search is same as the previous post and time complexity for it is O(n).

[ad type=”banner”]