C++で2次元文字配列内の指定文字列の出現回数をカウントする方法

以下の問題は、日刊紙のクロスワードパズルを模した例題です。ここでは2次元文字配列(マトリックス)が与えられ、その中から指定された単語を見つけ出すことが課題となります。探索アルゴリズムは、上から下(Top-to-Bottom)、右から左(Right-to-Left)、およびそれぞれの逆方向に個々の文字を辿っていきますが、斜め方向は探索対象外である点に注意してください。

例で理解しよう

入力- 検索文字列 word:LAYS

2次元文字配列 - { "LOAPYS", "KAYSOT", "LAYSST", "MLVAYS", "LAYSAA", "LAOYLS" };

出力- 2次元文字配列内の指定文字列の出現回数:7

説明- 文字列の配列が与えられ、その中から「LAYS」という単語を探します。検索は上から下、右から左、下から上、左から右の任意の方向に行うことができます。コード内のカウンターフラグは、検索文字列が見つかるたびに加算され、最終的な合計値が結果として返されます。この例では、「LAYS」が7回形成されていることがわかります。

1->LOAPYS - LAYS(左から右)

2->SAYAOL - LAYS(右から左)

3->LAYSST - LAYS(左から右)

4->MLVAYS - LAYS(左から右)

5->LAYSAA - LAYS(左から右)

6->LAOYLS - LAYS(左から右)

7->(下から上方向)赤色で示したLAYS

入力- 検索文字列 word:CAMP

2次元文字配列 - { "BLOOKS", "BPOOLK", "KOHPKB", "BOLKOK", "LKIOOB", "LAHYBL" }

出力- 2次元文字配列内の指定文字列の出現回数:0

説明: 同様に文字列配列の中から指定された単語を全方向(上から下、右から左、下から上、左から右)に検索します。この例では、該当する単語が一つも見つからないため、カウントは0となります。

プログラムで使用するアプローチ

• 検索対象の文字列(word)と文字列配列を、ユーティリティ変数とともにfindString()関数へ渡して処理を開始します。
• マトリックス内のすべてのセルを走査し、文字列の開始点となり得る文字を1つずつ選択します。
• 選択した文字を起点として、アルゴリズムに従い上下左右のすべての可能な方向へ再帰的に指定文字列を検索します。
• 一致が見つかった場合には、カウンターをインクリメントします。
• 最初の開始文字での処理が完了したら、次の文字に対して同じ処理を繰り返します。
• すべての一致に対応するカウントの合計を計算します。
• 最終的な答えを取得し、結果を出力します。

実装例

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

int utilitySearch(string word, int r, int c, string arr[], int maxR, int maxC, int index) {
    int count = 0;
    if (r >= 0 && r <= maxR && c >= 0) {
        if (c <= maxC && word[index] == arr[r][c]) {
            char res = word[index];
            index = index + 1;
            arr[r][c] = 0;
            if (word[index] == 0) {
                count = 1;
            } else {
                count = count + utilitySearch(word, r, c + 1, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r, c - 1, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r + 1, c, arr, maxR, maxC, index);
                count = count + utilitySearch(word, r - 1, c, arr, maxR, maxC, index);
            }
            arr[r][c] = res;
        }
    }
    return count;
}

int findString(string word, int r, int c, string str[], int countR, int countC) {
    int count = 0;
    for (int i = 0; i < countR; ++i) {
        for (int j = 0; j < countC; ++j) {
            count = count + utilitySearch(word, i, j, str, countR - 1, countC - 1, 0);
        }
    }
    return count;
}

int main() {
    string word = "FLOOD";
    string inp[] = {"FPLIOKOD", "FLOODYUT", "YFLOODPU", "FMLOSODT", "FILPOYOD", "FLOOOODE"};
    string str[(sizeof(inp) / sizeof(*inp))];
    for (int i = 0; i < (sizeof(inp) / sizeof(*inp)); ++i) {
        str[i] = inp[i];
    }
    cout << "Count of number of given string in 2D character array: "
         << findString(word, 0, 0, str, (sizeof(inp) / sizeof(*inp)), str[0].size());
    return 0;
}

上記のコードを実行すると、以下の出力が生成されます。

出力

Count of number of given string in 2D character array: 6

このように、再帰的な深さ優先探索を用いることで、2次元文字配列内に指定文字列が何回出現するかを効率的に数えることができます。各セルを起点として4方向への再帰呼び出しを行い、訪問済みのセルを一時的に無効化することで同じ文字を重複して使わないようにしているのがポイントです。