{"id":25492,"date":"2017-10-25T19:47:41","date_gmt":"2017-10-25T14:17:41","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=25492"},"modified":"2017-10-25T19:47:41","modified_gmt":"2017-10-25T14:17:41","slug":"c-programming-pattern-searching-set-6-efficient-construction-finite-automata-2","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/c-programming-pattern-searching-set-6-efficient-construction-finite-automata-2\/","title":{"rendered":"C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata"},"content":{"rendered":"

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.<\/p>\n

\"C-C<\/p>\n

\"C<\/p>\n

The abvoe diagrams represent graphical and tabular representations of pattern ACACAGA.<\/p>\n

Algorithm:<\/strong>
\n1) 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.
\n2) Initialize lps as 0. lps for the first index is always 0.
\n3) Do following for rows at index i = 1 to M. (M is the length of the pattern)
\n\u2026..a) Copy the entries from the row at index equal to lps.
\n\u2026..b) Update the entry for pat[i] character to i+1.
\n\u2026..c) Update lps \u201clps = TF[lps][pat[i]]\u201d where TF is the 2D array which is being constructed.<\/p>\n[ad type=”banner”]\n

Implementation<\/strong>
\nFollowing is C implementation for the above algorithm.<\/p>\n

C<\/span> <\/div> 
#include<stdio.h>#include<string.h>#define NO_OF_CHARS 256 \/* This function builds the TF table which represents Finite Automata for a   given pattern  *\/void computeTransFun(char *pat, int M, int TF[][NO_OF_CHARS]){    int i, lps = 0, x;     \/\/ Fill entries in first row    for (x =0; x < NO_OF_CHARS; x++)       TF[0][x] = 0;    TF[0][pat[0]] = 1;     \/\/ Fill entries in other rows    for (i = 1; i<= M; i++)    {        \/\/ Copy values from row at index lps        for (x = 0; x < NO_OF_CHARS; x++)            TF[i][x] = TF[lps][x];         \/\/ Update the entry corresponding to this character        TF[i][pat[i]] = i + 1;         \/\/ Update lps for next row to be filled        if (i < M)          lps = TF[lps][pat[i]];    }} \/* Prints all occurrences of pat in txt *\/void search(char *pat, char *txt){    int M = strlen(pat);    int N = strlen(txt);     int TF[M+1][NO_OF_CHARS];     computeTransFun(pat, M, TF);     \/\/ process text over FA.    int i, j=0;    for (i = 0; i < N; i++)    {       j = TF[j][txt[i]];       if (j == M)       {         printf ("\\n pattern found at index %d", i-M+1);       }    }} \/* Driver program to test above function *\/int main(){    char *txt = "GEEKS FOR GEEKS";    char *pat = "GEEKS";    search(pat, txt);    getchar();    return 0;}<\/code><\/pre> <\/div>\n
Output:<\/p>\n
 pattern found at index 0\r\n pattern found at index 10\r\n<\/pre>\n
Time Complexity for FA construction is O(M*NO_OF_CHARS). The code for search is same as the previous post<\/a> and time complexity for it is O(n).<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata – searching and sorting – FA construction method O((m^3)*NO_OF_CHARS).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,69866,1,71670],"tags":[73383,73480,73273,71808,73215,73492,73472,73490,73488,70940,73471,73473,73183,73194,73189,71799,73491,71774,71823,71775,73489,71796,73484,73229,73270,73317,73477,70957,73485,73481,70949,73474,73483,73479,73476,6910,70939,73482,73478,70945,73486,70950,73493,70272,70308,73475,73487,73184,73188,73316],"class_list":["post-25492","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-c-programming","category-coding","category-searching-and-sorting","tag-alphabet-pattern-programs-in-c","tag-automata-based-programming-examples","tag-best-pattern-matching-algorithm","tag-c-program-to-implement-lexical-analyser","tag-c-regular-expression","tag-definite-finite-automata","tag-dfa","tag-dfa-program-in-c-language","tag-finite-automata-to-regular-expression-examples","tag-java-regex","tag-java-regex-example","tag-java-regular-expression","tag-kmp","tag-kmp-algorithm","tag-knuth-algorithm","tag-lexical-analyser-in-c","tag-lexical-analyser-program-in-c","tag-lexical-analysis","tag-lexical-analysis-program-in-c","tag-lexical-analyzer","tag-lexical-analyzer-in-c","tag-lexical-analyzer-program-in-c","tag-lexical-analyzer-program-in-c-language-with-output","tag-pattern-matching","tag-pattern-matching-algorithm","tag-pattern-matching-program-in-c","tag-perl-match","tag-perl-regular-expression","tag-perl-regular-expression-match","tag-python-re-match-example","tag-python-regex-example","tag-python-regular-expression-example","tag-re-match-python-example","tag-regex-java","tag-regular","tag-regular-expression","tag-regular-expression-in-java","tag-regular-expression-in-perl","tag-regular-expression-java","tag-regular-expression-php","tag-regular-expression-program-in-c","tag-regular-expression-python","tag-regular-expression-to-finite-automata-examples","tag-search-algorithms","tag-searching-c","tag-simple-express","tag-state-machine-pattern","tag-string-algorithms","tag-string-match","tag-string-pattern-programs-in-c"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25492","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25492"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25492\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25492"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25492"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25492"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}