{"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":"<p>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<p><img fetchpriority=\"high\" decoding=\"async\" class=\"aligncenter wp-image-25478 size-full\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Searching-for-Patterns-Set-5-Finite-Automata.png\" alt=\"C-C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata\" width=\"497\" height=\"181\" srcset=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Searching-for-Patterns-Set-5-Finite-Automata.png 497w, https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Searching-for-Patterns-Set-5-Finite-Automata-300x109.png 300w\" sizes=\"(max-width: 497px) 100vw, 497px\" \/><\/p>\n<p><img decoding=\"async\" class=\"aligncenter size-full wp-image-25479\" src=\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/Searching-for-Patterns-Set-5-Finite-Automata2.png\" alt=\"C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata\" width=\"154\" height=\"188\" \/><\/p>\n<p>The abvoe diagrams represent graphical and tabular representations of pattern ACACAGA.<\/p>\n<p><strong>Algorithm:<\/strong><br \/>\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.<br \/>\n2) Initialize lps as 0. lps for the first index is always 0.<br \/>\n3) Do following for rows at index i = 1 to M. (M is the length of the pattern)<br \/>\n\u2026..a) Copy the entries from the row at index equal to lps.<br \/>\n\u2026..b) Update the entry for pat[i] character to i+1.<br \/>\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=\u201dbanner\u201d]\n<p><strong>Implementation<\/strong><br \/>\nFollowing is C implementation for the above algorithm.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%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\u201d message=\u201dC\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n<p>Output:<\/p>\n<pre> pattern found at index 0\r\n pattern found at index 10\r\n<\/pre>\n<p>Time Complexity for FA construction is O(M*NO_OF_CHARS). The code for search is same as the <a href=\"http:\/\/www.geeksforgeeks.org\/archives\/18919\">previous post<\/a> and time complexity for it is O(n).<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"<p>C programming for Pattern Searching Set 6 Efficient Construction of Finite Automata &#8211; searching and sorting &#8211; 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}]}}