C++で指定されたパワーを持つ部分文字列を効率的に検索する方法

問題概要

この問題では、文字列 str と整数 pow が与えられ、指定されたパワーを持つ部分文字列を見つけることが求められます。

具体的には、パワーの合計が pow と一致する部分文字列を返す必要があります。

文字列のパワーとは、その文字列に含まれる各文字のパワーの総和として定義されます。

各文字のパワーは次のように対応しています:a → 1、b → 2、c → 3 …(アルファベットの出現順に対応)

問題を理解するための例

入力 : string = "programming"、power = 49
出力 : 'pro'

解説 −

部分文字列 "pro" のパワー:
power(p) = 16
power(r) = 18
power(o) = 15
合計 = 16 + 18 + 15 = 49

解法アプローチ

最もシンプルな解法は二重ループ(ネストしたループ)を使う方法です。外側のループで文字列を走査し、内側のループで部分文字列を生成します。各部分文字列についてパワーを計算し、pow と一致すれば true を、最後まで見つからなければ false を返します。ただしこの方法は計算量が O(n²) となるため、長い文字列には不向きです。

より効率的なアプローチは、ハッシュマップ(unordered_map)を使って累積パワーを記録する方法です。文字列を先頭から走査しながら現在位置までの累積パワー(currPower)を計算し、「currPower − pow」という値がマップに既に存在するかどうかを確認します。存在する場合、その記録位置の次の文字から現在位置までの部分文字列が、まさに目的のパワーを持つことになります。これは「接頭辞和(prefix sum)」の考え方を応用した手法で、計算量を O(n) に抑えられるのが大きな利点です。

アルゴリズム

• ステップ1 − 文字列を走査し、累積パワー(currPow)を計算します。

• ステップ2 − 値(currPow − pow)がマップに存在するかどうかを確認します。

  • ステップ2.1 − 存在する場合は、対応する部分文字列を出力して終了します。

• ステップ3 − currPow の値をマップに挿入します。

• ステップ4 − 文字列のすべての文字を走査しても該当する部分文字列が見つからない場合は、「not possible(該当なし)」と出力します。

実装例

以下は、この解法の動作を示す C++ プログラムです。

#include <bits/stdc++.h>
using namespace std;
void findSubStringWithPower(string str, int power) {
   int i;
   unordered_map<int , int > powerSS;
   int currPower = 0;
   int N = str.length();
   for (i = 0; i < N; i++) {
      currPower = currPower + (str[i] - 'a' + 1);
      if (currPower == power) {
         cout<<"Substring : "<<str.substr((0), i+1)<<" has power "<<power;
         return;
      }
      if (powerSS.find(currPower - power) != powerSS.end()) {
         cout<<"Substring from index "<<str.substr((powerSS[currPower-power] + 1),(i - (powerSS[currPower - power] + 1)) + 1);
         cout<<" has power "<<power; return;
      }
      powerSS[currPower] = i;
   }
   cout<<"No substring found!";
}
int main() {
   string str = "programming";
   int power = 49;
   findSubStringWithPower(str, power);
   return 0;
}

出力結果

Substring : pro has power 49

まとめ

このアルゴリズムは、文字列を一度だけ走査すればよいため、時間計算量は O(n)、ハッシュマップに累積パワーを格納するため空間計算量も O(n) となります。単純な全探索(O(n²))と比べて大幅に高速であり、長い文字列に対しても実用的な解法です。