C++で括弧文字列からイコールポイント（等分点）を見つける方法

この記事では、C++を使って括弧の文字列からイコールポイント（等分点）を求める方法を解説します。

イコールポイントとは？

イコールポイントとは、あるインデックス i において、その位置より前にある開き括弧「(」の数と、その位置以降にある閉じ括弧「)」の数が等しくなる地点のことです。

例として、次の括弧文字列を考えてみましょう。

(()))( ()()() )) ) → 元の文字列は "(()))(()()())))"

この文字列を詳しく観察すると、インデックス0〜9の範囲に含まれる開き括弧は5個、インデックス9〜14の範囲に含まれる閉じ括弧も5個あります。したがって、インデックス9がこの文字列のイコールポイントであることがわかります。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

• 文字列の先頭から各インデックス i までに出現する開き括弧「(」の累積個数を配列に記録する
• 文字列の末尾から逆順に走査し、各インデックス i 以降に出現する閉じ括弧「)」の累積個数を配列に記録する
• 開き括弧の数と閉じ括弧の数が一致するインデックスを探す

この方法では、前処理にO(n)、探索にもO(n)しかかからないため、全体の計算量はO(n)となり、非常に効率的です。

C++による実装例

#include<iostream>
#include<cmath>
using namespace std;

int findEqualPoint(string str) {
    int total_length = str.length();
    int open[total_length+1] = {0}, close[total_length+1] = {0};
    int index = -1;
    open[0] = 0;
    close[total_length] = 0;

    // 先頭の文字が開き括弧なら open[1] を1に設定
    if (str[0]=='(')
        open[1] = 1;

    // 末尾の文字が閉じ括弧なら close[end] を1に設定
    if (str[total_length-1] == ')')
        close[total_length-1] = 1;

    // 各位置までの開き括弧の累積数を計算
    for (int i = 1; i < total_length; i++) {
        if ( str[i] == '(' )
            open[i+1] = open[i] + 1;
        else
            open[i+1] = open[i];
    }

    // 各位置以降の閉じ括弧の累積数を逆順に計算
    for (int i = total_length-2; i >= 0; i--) {
        if ( str[i] == ')' )
            close[i] = close[i+1] + 1;
        else
            close[i] = close[i+1];
    }

    // 開き括弧が一切ない場合は先頭が答え
    if (open[total_length] == 0)
        return total_length;

    // 閉じ括弧が一切ない場合は末尾が答え
    if (close[0] == 0)
        return 0;

    // 開き括弧と閉じ括弧の数が一致するインデックスを検索
    for (int i=0; i<=total_length; i++)
        if (open[i] == close[i])
            index = i;

    return index;
}

int main() {
    string str = "(()))(()()())))";
    cout << "Index of equal point: " << findEqualPoint(str);
}

コードのポイント

• 配列 open[] には、各インデックスまでの開き括弧の累積数が格納されます。
• 配列 close[] には、各インデックス以降の閉じ括弧の累積数が格納されます。
• 該当するイコールポイントが存在しない場合は -1 が返されます。
• 開き括弧または閉じ括弧が片方しか存在しないエッジケースにも対応しています。

実行結果

Index of equal point: 9

入力文字列 "(()))(()()())))" の場合、インデックス9より前には開き括弧が5個、インデックス9以降には閉じ括弧が5個あるため、正しく 9 が出力されます。

まとめ

括弧文字列からイコールポイントを見つける問題は、開き括弧と閉じ括弧の累積カウントを前方向と後方向の2回の走査で求めることで、O(n)の時間計算量で効率的に解くことができます。累積和の考え方を応用した典型的なアルゴリズムなので、ぜひマスターしておきましょう。