C++で行列内のパターンの方向（水平・垂直）を検索する方法

この記事では、文字値で構成される行列（2次元配列）と、検索対象となるパターンが与えられたとき、そのパターンが行列の中で水平方向と垂直方向のどちらに存在するのかを判定する問題を解説します。

問題の例

具体的な入力と出力を見てみましょう。

入力

mat[][] = {
    { r, a, m },
    { a, m, c },
    { w, f, t }
}
Pattern : raw

出力

vertical

この例では、パターン「raw」は1列目に上から下へ向かって「r → a → w」と並んでいるため、垂直方向に存在すると判定されます。

解法アプローチ

最も単純な解法は、行列のN行すべてに対して長さMのパターンを線形探索することです。この方法でも動作しますが、計算量が大きくなりやすいという欠点があります。

そこでより効率的なのが、文字列検索に優れたKMP（Knuth–Morris–Pratt）パターンマッチングアルゴリズムを利用する方法です。KMPを使えば、失敗関数（LPS配列）を事前に構築しておくことで、テキストの走査中に照合位置を後戻りせずに済むため、O(N + M) の時間計算量で高速な検索が可能になります。

実装の流れは以下の通りです。

• まずLPS配列を計算する関数 calcLpsValues() を用意します。
• searchPattern() 関数で、1行（または1列）の文字列に対してKMP検索を行い、パターンが見つかれば1を返します。
• findPatternOrientation() 関数では、各行を横方向のテキストとして検索し、見つかれば「horizontal」を出力します。
• 同時に、各列の文字を取り出して縦方向の文字列を作成し、検索して見つかれば「vertical」を出力します。

C++での実装例

#include<bits/stdc++.h>
using namespace std;
#define N 3

// LPS（最長接頭辞でもある接尾辞）配列を計算する関数
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;
        }
    }
}

// KMPアルゴリズムによるパターン検索
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;
}

// パターンの方向（水平 or 垂直）を判定する関数
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

まとめ

このように、行列の各行と各列をそれぞれ文字列として扱い、KMPアルゴリズムでパターンを検索することで、パターンが水平方向と垂直方向のどちらに存在するかを効率的に判定できます。素朴な全探索よりも計算量を抑えられるため、大きな行列や長いパターンを扱う場合に特に有効な手法です。