Given a matrix of characters and a pattern, find the orientation of pattern in the matrix. In other words, find if pattern appears in matrix in horizontal or vertical direction. Achieve this in minimum time possible.<\/p>\n
Input:\r\nmat[N][N] = { {'a', 'b', 'c', 'd', 'e'},\r\n {'f', 'g', 'h', 'i', 'j'},\r\n {'k', 'l', 'm', 'n', 'o'},\r\n {'p', 'q', 'r', 's', 't'},\r\n {'u', 'v', 'w', 'x', 'y'}};\r\npattern = \"pqrs\";\r\n\r\nOutput: Horizontal<\/pre>\n[ad type=\u201dbanner\u201d]\nA simple solution is for each row and column, use Naive pattern searching algorithm to find the orientation of pattern in the matrix. The time complexity of Naive pattern searching algorithm for every row is O(NM) where N is size of the matrix and M is length of the pattern. So, the time complexity of this solution will be O(N*(NM))<\/strong> as each of N rows and N columns takes O(NM) time.<\/p>\nCan we do better?<\/strong>
\nThe idea is to use KMP pattern matching algorithm for each row and column. The KMP matching algorithm improves the worst case to O(N + M). The total cost of a KMP search is linear in the number of characters of string and pattern. For a N x N matrix and pattern of length M, complexity of this solution will be O(N*(N+M))<\/strong> as each of N rows and N columns will take O(N + M) time.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20for%20finding%20orientation%20of%20the%20pattern%0A%2F%2F%20using%20KMP%20pattern%20searching%20algorithm%0A%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%23include%3Cstdlib.h%3E%0A%23define%20N%205%0A%20%0A%2F%2F%20Used%20in%20KMP%20Search%20for%20preprocessing%20the%20pattern%0Avoid%20computeLPSArray(char%20*pat%2C%20int%20M%2C%20int%20*lps)%0A%7B%0A%20%20%20%20%2F%2F%20length%20of%20the%20previous%20longest%20prefix%20suffix%0A%20%20%20%20int%20len%20%3D%200%3B%0A%20%20%20%20int%20i%20%3D%201%3B%0A%20%0A%20%20%20%20lps%5B0%5D%20%3D%200%3B%20%2F%2F%20lps%5B0%5D%20is%20always%200%0A%20%0A%20%20%20%20%2F%2F%20the%20loop%20calculates%20lps%5Bi%5D%20for%20i%20%3D%201%20to%20M-1%0A%20%20%20%20while%20(i%20%3C%20M)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(pat%5Bi%5D%20%3D%3D%20pat%5Blen%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20len%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20lps%5Bi%2B%2B%5D%20%3D%20len%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20else%20%2F%2F%20(pat%5Bi%5D%20!%3D%20pat%5Blen%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(len%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20This%20is%20tricky.%20Consider%20the%20example%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20AAACAAAA%20and%20i%20%3D%207.%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20len%20%3D%20lps%5Blen-1%5D%3B%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Also%2C%20note%20that%20we%20do%20not%20increment%20i%20here%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%20%20%20%20else%20%2F%2F%20if%20(len%20%3D%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20lps%5Bi%2B%2B%5D%20%3D%200%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%7D%0A%20%0Aint%20KMPSearch(char%20*pat%2C%20char%20*txt)%0A%7B%0A%20%20%20%20int%20M%20%3D%20strlen(pat)%3B%0A%20%0A%20%20%20%20%2F%2F%20create%20lps%5B%5D%20that%20will%20hold%20the%20longest%20prefix%20suffix%0A%20%20%20%20%2F%2F%20values%20for%20pattern%0A%20%20%20%20int%20*lps%20%3D%20(int%20*)malloc(sizeof(int)*M)%3B%0A%20%20%20%20int%20j%20%3D%200%3B%20%2F%2F%20index%20for%20pat%5B%5D%0A%20%0A%20%20%20%20%2F%2F%20Preprocess%20the%20pattern%20(calculate%20lps%5B%5D%20array)%0A%20%20%20%20computeLPSArray(pat%2C%20M%2C%20lps)%3B%0A%20%0A%20%20%20%20int%20i%20%3D%200%3B%20%2F%2F%20index%20for%20txt%5B%5D%0A%20%20%20%20while%20(i%20%3C%20N)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(pat%5Bj%5D%20%3D%3D%20txt%5Bi%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20j%2B%2B%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20i%2B%2B%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20if%20(j%20%3D%3D%20M)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20return%201%20is%20pattern%20is%20found%0A%20%20%20%20%20%20%20%20%20%20%20%20return%201%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20%2F%2F%20mismatch%20after%20j%20matches%0A%20%20%20%20%20%20%20%20else%20if%20(i%20%3C%20N%20%26%26%20pat%5Bj%5D%20!%3D%20txt%5Bi%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20Do%20not%20match%20lps%5B0..lps%5Bj-1%5D%5D%20characters%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20they%20will%20match%20anyway%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(j%20!%3D%200)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20j%20%3D%20lps%5Bj-1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20else%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%3D%20i%2B1%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%20%20%20free(lps)%3B%20%2F%2F%20to%20avoid%20memory%20leak%0A%20%20%20%20%2F%2F%20return%200%20is%20pattern%20is%20not%20found%0A%20%20%20%20return%200%3B%0A%7D%0A%20%0A%2F%2F%20Function%20to%20find%20orientation%20of%20pattern%20in%20the%20matrix%0A%2F%2F%20It%20uses%20KMP%20pattern%20searching%20algorithm%0Avoid%20findOrientation(char%20mat%5B%5D%5BN%5D%2C%20char%20*pat)%0A%7B%0A%20%20%20%20%2F%2F%20allocate%20memory%20for%20string%20contaning%20cols%0A%20%20%20%20char%20*col%20%3D%20(char*)%20malloc(N)%3B%0A%20%0A%20%20%20%20for%20(int%20i%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%20%20%2F%2F%20search%20in%20row%20i%0A%20%20%20%20%20%20%20%20if%20(KMPSearch(pat%2C%20mat%5Bi%5D))%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22Horizontal%5Cn%22)%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Construct%20an%20array%20to%20store%20i\u2019th%20column%0A%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20N%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20col%5Bj%5D%20%3D%20*(mat%5Bj%5D%20%2B%20i)%3B%0A%20%0A%20%20%20%20%20%20%20%20%2F%2F%20Search%20in%20column%20i%0A%20%20%20%20%20%20%20%20if%20(KMPSearch(pat%2C%20col))%0A%20%20%20%20%20%20%20%20%20%20%20%20printf(%22Vertical%5Cn%22)%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20to%20avoid%20memory%20leak%0A%20%20%20%20free(col)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20char%20mat%5BN%5D%5BN%5D%20%3D%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%7B\u2019a\u2019%2C%20\u2019b\u2019%2C%20\u2019c\u2019%2C%20\u2019d\u2019%2C%20\u2019e\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u2019f\u2019%2C%20\u2019g\u2019%2C%20\u2019h\u2019%2C%20\u2019i\u2019%2C%20\u2019j\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u2019k\u2019%2C%20\u2019l\u2019%2C%20\u2019m\u2019%2C%20\u2019n\u2019%2C%20\u2019o\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u2019p\u2019%2C%20\u2019q\u2019%2C%20\u2019r\u2019%2C%20\u2019s\u2019%2C%20\u2019t\u2019%7D%2C%0A%20%20%20%20%20%20%20%20%7B\u2019u\u2019%2C%20\u2019v\u2019%2C%20\u2019w\u2019%2C%20\u2019x\u2019%2C%20\u2019y\u2019%7D%0A%20%0A%20%20%20%20%7D%3B%0A%20%20%20%20char%20pat%5B%5D%20%3D%20%22pqrs%22%3B%0A%20%0A%20%20%20%20findOrientation(mat%2C%20pat)%3B%0A%20%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC Program\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\nOutput :<\/strong><\/p>\nHorizontal<\/pre>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"C Programming-Find orientation of a pattern in a matrix – Matrix – Given a matrix of characters and a pattern, find the orientation of pattern<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83529,82291],"tags":[83537,66753,83530,83540,83541,83539,83542,83543,83534,83531,83532,83544,83538,83535,83533,83545,83536],"class_list":["post-28327","post","type-post","status-publish","format-standard","hentry","category-geometric","category-matrix","tag-2-in-place-rotation-of-2d-array-by-90-degree-clockwise","tag-android-orientation","tag-bfs-in-2d-matrix","tag-drawaspatterninrect","tag-glitch-in-the-matrix","tag-in-orientation","tag-inverse-matrix-in-r","tag-matrix-in-excel","tag-matrix-rotation-java","tag-matrix-transpose-geeksforgeeks","tag-maze-shortest-path-c","tag-orientation","tag-pattern-matrix","tag-rotate-matrix-c","tag-rotation-matrix-anticlockwise-in-c","tag-sector","tag-you-are-given-an-nxn-2d-matrix-representing-an-image-rotate-the-image-by-90-degrees-clockwise"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28327","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=28327"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/28327\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=28327"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=28327"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=28327"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}