给定一个字符矩阵和一个模式，找出模式在矩阵中的方向。换句话说，找出模式是在水平方向还是垂直方向出现在矩阵中。在尽可能短的时间内实现这一点。
null
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
我们强烈建议您尽量减少浏览器，并先自己尝试。 一个简单的解决方案是，对于每一行和每一列，使用 朴素模式搜索算法 找到矩阵中图案的方向。朴素模式搜索算法每行的时间复杂度为O（NM），其中N是矩阵的大小，M是模式的长度。因此，该解决方案的时间复杂性将是 O（N*（纳米）） 因为N行和N列中的每一行都需要O（NM）的时间。
我们能做得更好吗？ 这个想法是使用 KMP模式匹配算法 对于每一行和每一列。KMP匹配算法将最坏情况改进为O（N+M）。KMP搜索的总成本与字符串和模式的字符数成线性关系。对于nxn矩阵和长度为M的模式，这个解的复杂性将是 O（N*（N+M）） 因为N行和N列中的每一行都需要O（N+M）时间。
C++
// C++ program for finding orientation of the pattern // using KMP pattern searching algorithm #include<bits/stdc++.h> using namespace std; #define N 5 // Used in KMP Search for preprocessing the pattern void computeLPSArray( char *pat, int M, int *lps) { // length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i++] = len; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the example // AAACAAAA and i = 7. len = lps[len - 1]; // Also, note that we do not increment i here } else // if (len == 0) { lps[i++] = 0; } } } } int KMPSearch( char *pat, char *txt) { int M = strlen (pat); // create lps[] that will hold the longest // prefix suffix values for pattern int *lps = ( int *) malloc ( sizeof ( int )*M); int j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); int i = 0; // index for txt[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { // return 1 is pattern is found return 1; } // mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) j = lps[j - 1]; else i = i + 1; } } free (lps); // to avoid memory leak // return 0 is pattern is not found return 0; } // Function to find orientation of pattern in the matrix // It uses KMP pattern searching algorithm void findOrientation( char mat[][N], char *pat) { // allocate memory for string containing cols char *col = ( char *) malloc (N); for ( int i = 0; i < N; i++) { // search in row i if (KMPSearch(pat, mat[i])) { cout << "Horizontal" << endl; return ; } // Construct an array to store i'th column for ( int j = 0; j < N; j++) col[j] = *(mat[j] + i); // Search in column i if (KMPSearch(pat, col)) cout << "Vertical" << endl; } // to avoid memory leak free (col); } // Driver Code int main() { char 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' }}; char pat[] = "pqrs" ; findOrientation(mat, pat); return 0; } // This code is contributed by kumar65 |
C
// C program for finding orientation of the pattern // using KMP pattern searching algorithm #include<stdio.h> #include<string.h> #include<stdlib.h> #define N 5 // Used in KMP Search for preprocessing the pattern void computeLPSArray( char *pat, int M, int *lps) { // length of the previous longest prefix suffix int len = 0; int i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i++] = len; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the example // AAACAAAA and i = 7. len = lps[len-1]; // Also, note that we do not increment i here } else // if (len == 0) { lps[i++] = 0; } } } } int KMPSearch( char *pat, char *txt) { int M = strlen (pat); // create lps[] that will hold the longest prefix suffix // values for pattern int *lps = ( int *) malloc ( sizeof ( int )*M); int j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); int i = 0; // index for txt[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { // return 1 is pattern is found return 1; } // mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) j = lps[j-1]; else i = i+1; } } free (lps); // to avoid memory leak // return 0 is pattern is not found return 0; } // Function to find orientation of pattern in the matrix // It uses KMP pattern searching algorithm void findOrientation( char mat[][N], char *pat) { // allocate memory for string containing cols char *col = ( char *) malloc (N); for ( int i = 0; i < N; i++) { // search in row i if (KMPSearch(pat, mat[i])) { printf ( "Horizontal" ); return ; } // Construct an array to store i'th column for ( int j = 0; j < N; j++) col[j] = *(mat[j] + i); // Search in column i if (KMPSearch(pat, col)) printf ( "Vertical" ); } // to avoid memory leak free (col); } // Driver program to test above function int main() { char 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' } }; char pat[] = "pqrs" ; findOrientation(mat, pat); return 0; } |
JAVA
// Java program for finding orientation of the pattern // using KMP pattern searching algorithm import java.io.*; import java.util.*; class GFG { public static int N = 5 ; // Used in KMP Search for preprocessing the pattern public static void computeLPSArray( char pat[], int M, int lps[]) { // length of the previous longest prefix suffix int len = 0 ; int i = 1 ; lps[ 0 ] = 0 ; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i++] = len; } else // (pat[i] != pat[len]) { if (len != 0 ) { // This is tricky. Consider the example // AAACAAAA and i = 7. len = lps[len - 1 ]; // Also, note that we do not increment i here } else // if (len == 0) { lps[i++] = 0 ; } } } } public static int KMPSearch( char pat[], char txt[]) { int M = pat.length; // create lps[] that will hold the longest // prefix suffix values for pattern int [] lps = new int [M]; int j = 0 ; // index for pat[] // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); int i = 0 ; // index for txt[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { // return 1 is pattern is found return 1 ; } // mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0 ) { j = lps[j - 1 ]; } else { i = i + 1 ; } } } // return 0 is pattern is not found return 0 ; } // Function to find orientation of pattern in the matrix // It uses KMP pattern searching algorithm public static void findOrientation( char mat[][], char pat[]) { // allocate memory for string containing cols char [] col = new char [N]; for ( int i = 0 ; i < N; i++) { // search in row i if (KMPSearch(pat, mat[i]) == 1 ) { System.out.println( "Horizontal" ); return ; } // Construct an array to store i'th column for ( int j = 0 ; j < N; j++) { col[j] = mat[j][i]; } // Search in column i if (KMPSearch(pat, col) == 1 ) { System.out.println( "Vertical" ); } } } // Driver Code public static void main (String[] args) { char [][] mat = { { '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' }}; char pat[] = { 'p' , 'q' , 'r' , 's' }; findOrientation(mat, pat); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python3 program for finding orientation of the pattern # using KMP pattern searching algorithm N = 5 # Used in KMP Search for preprocessing the pattern def computeLPSArray(pat, M, lps): # length of the previous longest prefix suffix lenl = 0 i = 1 lps[ 0 ] = 0 # lps[0] is always 0 # the loop calculates lps[i] for i = 1 to M-1 while (i < M): if (pat[i] = = pat[lenl]): lenl + = 1 lps[i] = lenl i + = 1 else : # (pat[i] != pat[lenl]) if (lenl ! = 0 ) : # This is tricky. Consider the example # AAACAAAA and i = 7. lenl = lps[lenl - 1 ] # Also, note that we do not increment i here # if (lenl == 0) else : lps[i] = 0 i + = 1 def KMPSearch(pat, txt): M = len (pat) # create lps[] that will hold the longest # prefix suffix values for pattern lps = [ 0 ] * M j = 0 # index for pat[] # Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps) # index for txt[] i = 0 while (i < N): if (pat[j] = = txt[i]): j + = 1 i + = 1 if (j = = M): # return 1 is pattern is found return 1 # mismatch after j matches elif (i < N and pat[j] ! = txt[i]): # Do not match lps[0..lps[j-1]] characters, # they will match anyway if (j ! = 0 ): j = lps[j - 1 ] else : i = i + 1 # to amemory leak # return 0 is pattern is not found return 0 # Function to find orientation of pattern in the matrix # It uses KMP pattern searching algorithm def findOrientation(mat, pat): # allocate memory for string containing cols col = [ 'a' ] * (N) for i in range (N): # search in row i if (KMPSearch(pat, mat[i])): print ( "Horizontal" ) return # Construct an array to store i'th column for j in range (N): col[j] = mat[j][i] # Search in column i if (KMPSearch(pat, col)): print ( "Vertical" ) # Driver Code mat = [[ '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' ]] pat = "pqrs" findOrientation(mat, pat) # This code is contributed by Mohit kumar 29 |
C#
// C# program for finding orientation of // the pattern using KMP pattern searching // algorithm using System; class GFG{ public static int N = 5; // Used in KMP Search for preprocessing the pattern public static void computeLPSArray( char [] pat, int M, int [] lps) { // Length of the previous longest // prefix suffix int len = 0; int i = 1; // lps[0] is always 0 lps[0] = 0; // The loop calculates lps[i] // for i = 1 to M-1 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i++] = len; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the // example AAACAAAA and i = 7. len = lps[len - 1]; // Also, note that we do not // increment i here } // If (len == 0) else { lps[i++] = 0; } } } } public static int KMPSearch( char [] pat, char [] txt) { int M = pat.Length; // Create lps[] that will hold the longest // prefix suffix values for pattern int [] lps = new int [M]; int j = 0; // index for pat[] // Preprocess the pattern // (calculate lps[] array) computeLPSArray(pat, M, lps); int i = 0; // index for txt[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { // Return 1 is pattern is found return 1; } // Mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] // characters, they will match anyway if (j != 0) { j = lps[j - 1]; } else { i = i + 1; } } } // Return 0 is pattern is not found return 0; } // Function to find orientation of pattern // in the matrix. It uses KMP pattern // searching algorithm public static void findOrientation( char [,] mat, char [] pat) { // Allocate memory for string // containing cols char [] col = new char [N]; for ( int i = 0; i < N; i++) { // Allocate memory for string // containing rows char [] row = new char [mat.GetLength(1)]; for ( int j = 0; j < mat.GetLength(1); j++) { row[j] = mat[i, j]; } // Search in row i if (KMPSearch(pat, row) == 1) { Console.WriteLine( "Horizontal" ); return ; } // Construct an array to store // i'th column for ( int j = 0; j < N; j++) { col[j] = mat[j,i]; } // Search in column i if (KMPSearch(pat, col) == 1) { Console.WriteLine( "Vertical" ); } } } // Driver Code static public void Main() { char [,] mat = { { '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' } }; char [] pat = { 'p' , 'q' , 'r' , 's' }; findOrientation(mat, pat); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript program for finding orientation of the pattern // using KMP pattern searching algorithm let N = 5; // Used in KMP Search for preprocessing the pattern function computeLPSArray(pat,M,lps) { // length of the previous longest prefix suffix let len = 0; let i = 1; lps[0] = 0; // lps[0] is always 0 // the loop calculates lps[i] for i = 1 to M-1 while (i < M) { if (pat[i] == pat[len]) { len++; lps[i++] = len; } else // (pat[i] != pat[len]) { if (len != 0) { // This is tricky. Consider the example // AAACAAAA and i = 7. len = lps[len - 1]; // Also, note that we do not increment i here } else // if (len == 0) { lps[i++] = 0; } } } } function KMPSearch(pat,txt) { let M = pat.length; // create lps[] that will hold the longest // prefix suffix values for pattern let lps = new Array(M); let j = 0; // index for pat[] // Preprocess the pattern (calculate lps[] array) computeLPSArray(pat, M, lps); let i = 0; // index for txt[] while (i < N) { if (pat[j] == txt[i]) { j++; i++; } if (j == M) { // return 1 is pattern is found return 1; } // mismatch after j matches else if (i < N && pat[j] != txt[i]) { // Do not match lps[0..lps[j-1]] characters, // they will match anyway if (j != 0) { j = lps[j - 1]; } else { i = i + 1; } } } // return 0 is pattern is not found return 0; } // Function to find orientation of pattern in the matrix // It uses KMP pattern searching algorithm function findOrientation(mat,pat) { // allocate memory for string containing cols let col = new Array(N); for (let i = 0; i < N; i++) { // search in row i if (KMPSearch(pat, mat[i]) == 1) { document.write( "Horizontal" ); return ; } // Construct an array to store i'th column for (let j = 0; j < N; j++) { col[j] = mat[j][i]; } // Search in column i if (KMPSearch(pat, col) == 1) { document.write( "Vertical" ); } } } // Driver Code let mat=[['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']]; let pat= "pqrs" ; findOrientation(mat, pat); // This code is contributed by unknown2108 </script> |
输出：
Horizontal
本文由 阿迪蒂亚·戈尔 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
