查找矩阵中图案的方向 · GeeksForGeeks 中文系列教程

# 查找矩阵中图案的方向 > 原文： [https://www.geeksforgeeks.org/find-orientation-of-a-pattern-in-a-matrix/](https://www.geeksforgeeks.org/find-orientation-of-a-pattern-in-a-matrix/) 给定一个字符矩阵和一个模式，请在矩阵中找到模式的方向。换句话说，找出图案是在水平方向还是垂直方向上出现在矩阵中。在尽可能短的时间内实现这一目标。 ``` 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 ``` **我们强烈建议您最小化浏览器，然后自己尝试。** 一个简单的解决方案是针对每一行和每一列，使用[朴素模式搜索算法](https://www.geeksforgeeks.org/searching-for-patterns-set-1-naive-pattern-searching/)查找矩阵中模式的方向。每行的朴素模式搜索算法的时间复杂度为 O（NM），其中 N 是矩阵的大小，M 是模式的长度。因此，此解决方案的时间复杂度将为 **O（N *（NM））**，因为 N 行和 N 列中的每一个都需要 O（NM）时间。 **我们可以做得更好吗？** 这个想法是针对每一行和每一列使用 [KMP 模式匹配算法](https://www.geeksforgeeks.org/searching-for-patterns-set-2-kmp-algorithm/)。 KMP 匹配算法将最坏情况改善为 O（N + M）。 KMP 搜索的总成本与字符串和模式的字符数成线性关系。对于 N x N 矩阵和长度为 M 的模式，此解决方案的复杂度将为 **O（N *（N + M））**，因为 N 行和 N 列中的每一个都将为 O（N + M）时间。 ## C++ ```cpp // 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 contaning 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 ```