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.
Input:
mat[N][N] = { {'a', 'b', 'c', 'd', 'e'},
{'f', 'g', 'h', 'i', 'j'},
{'k', 'l', 'm', 'n', 'o'},
{'p', 'q', 'r', 's', 't'},
{'u', 'v', 'w', 'x', 'y'}};
pattern = "pqrs";
Output: Horizontal
[ad type=”banner”]
A 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)) as each of N rows and N columns takes O(NM) time.
Can we do better?
The 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)) as each of N rows and N columns will take O(N + M) time.
[pastacode lang=”c” manual=”%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’th%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’a’%2C%20’b’%2C%20’c’%2C%20’d’%2C%20’e’%7D%2C%0A%20%20%20%20%20%20%20%20%7B’f’%2C%20’g’%2C%20’h’%2C%20’i’%2C%20’j’%7D%2C%0A%20%20%20%20%20%20%20%20%7B’k’%2C%20’l’%2C%20’m’%2C%20’n’%2C%20’o’%7D%2C%0A%20%20%20%20%20%20%20%20%7B’p’%2C%20’q’%2C%20’r’%2C%20’s’%2C%20’t’%7D%2C%0A%20%20%20%20%20%20%20%20%7B’u’%2C%20’v’%2C%20’w’%2C%20’x’%2C%20’y’%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” message=”C Program” highlight=”” provider=”manual”/]
Output :
Horizontal
[ad type=”banner”]