查找矩陣中圖案的方向 · 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 ```