数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律研究使用 C++ 在矩阵中查找模式的方向
本问题给定一个由字符值组成的矩阵，形成一个模式，还给定一个待查找的模式。我们的任务是找到一个模式在矩阵中的方向（水平或垂直）。
让我们通过一个例子来理解这个问题，
输入
mat[][] = {
{ r, a, m },
{a, m, c},
{w, f, t}
}
Patern : raw输出
vertical
解决方案方法
解决这个问题的一种简单的方法是，在矩阵的所有 N 行中搜索 M 大小的模式。该解决方案是可以接受的，但一种更有效的方法是，对矩阵的所有行和列使用 KML 模式匹配算法。
程序来说明我们的解决方案的工作原理，
示例
#include<bits/stdc++.h>
using namespace std;
#define N 3
void calcLpsValues(char *pat, int M, int *lps) {
int len = 0;
int i = 1;
lps[0] = 0;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i++] = len;
} else {
if (len != 0)
len = lps[len - 1];
else
lps[i++] = 0;
}
}
}
int searchPattern(char *pat, char *txt) {
int M = strlen(pat);
int *lps = (int *)malloc(sizeof(int)*M);
int j = 0;
calcLpsValues(pat, M, lps);
int i = 0;
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M)
return 1;
else if (i < N && pat[j] != txt[i]) {
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
return 0;
}
void findPatternOrientation(char mat[][N], char *pat) {
char *col = (char*) malloc(N);
for (int i = 0; i < N; i++) {
if (searchPattern(pat, mat[i])) {
cout<<"horizontal";
return;
}
for (int j = 0; j < N; j++)
col[j] = *(mat[j] + i);
if (searchPattern(pat, col))
cout<<"vertical";
}
}
int main() {
char mat[N][N] = {{'r', 'a', 'm'},
{'a', 'm', 'c'},
{'w', 'f', 't'}};
char pattern[] = "raw";
cout<<"The orientation of the pattern in matrix is ";
findPatternOrientation(mat, pattern);
return 0;
}输出
The orientation of the pattern in matrix is vertical
更新于：2021 年 3 月 16 日
112 次浏览
广告