【C++】文字列内に含まれるすべてのアナグラムの開始位置を検索する方法

問題概要

文字列 s と空でない文字列 p が与えられたとき、s の中に含まれる「p のアナグラム」が始まるすべての開始インデックスを求めるのがこの問題です。

文字列は小文字アルファベットのみで構成され、s と p の長さはそれぞれ 20 および 100 を超えないものとします。

たとえば、s = "cbaebabacd"、p = "abc" の場合、出力は [0, 6] となります。インデックス 0 の位置には "cba" があり、インデックス 6 の位置には "bac" があり、どちらも "abc" のアナグラムだからです。

解決のための手順

この問題は、スライディングウィンドウ（尺取り法）とマップを組み合わせることで効率的に解けます。具体的な手順は以下の通りです。

• マップ m を定義し、n := s のサイズ、left := 0、right := 0、counter := p のサイズとして初期化します。
• 結果を格納する配列 ans を定義します。
• p に含まれる各文字の出現回数をマップ m に記録します。
• right を 0 から n − 1 まで順に動かしながら処理を行います。
  • m に s[right] が存在し、かつ m[s[right]] が 0 でない場合は、m[s[right]] を 1 減らし、counter も 1 減らします。counter が 0 になったら、left を ans に追加します。
  • それ以外の場合は次のように処理します。
    • left < right の間、以下を繰り返します。
    • s[left] が m に存在しない場合は counter を 1 増やし、m[s[left]] を 1 増やします。
    • left を 1 増やします。
    • m に s[right] が存在し、かつ m[s[right]] が 0 でない場合は、right を 1 減らしてループを抜けます。
  • 最後に、m に s[left] が存在しない場合は left := right + 1 と設定します。
• すべての処理が終わったら ans を返します。

アルゴリズムのポイント

この手法では、p の各文字の必要な出現回数をマップで管理し、counter が「まだ満たされていない文字数」を表すようにしています。ウィンドウを右に拡張しながら条件を満たした瞬間に開始位置を記録し、不要な文字が出てきたときは左端を縮めていくことで、全体を O(n) の計算量で処理できます。

サンプルコード（C++）

以下に実際の実装例を示します。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
public:
   vector<int> findAnagrams(string s, string p) {
      map <char, int> m;
      int n = s.size();
      int left = 0, right = 0;
      int counter = p.size();
      vector <int> ans;
      for(int i = 0; i < p.size(); i++) m[p[i]]++;
      for(int right = 0; right < n; right++){
         if(m.find(s[right]) != m.end() && m[s[right]]){
            m[s[right]]--;
            counter--;
            if(counter == 0)ans.push_back(left);
         } else {
            while(left<right){
               if(m.find(s[left]) != m.end()) {
                  counter++;
                  m[s[left]]++;
               }
               left++;
               if(m.find(s[right]) != m.end() && m[s[right]]){
                  right--;
                  break;
               }
            }
            if(m.find(s[left])==m.end())left = right + 1;
         }
      }
      return ans;
   }
};
main(){
   Solution ob;
   print_vector(ob.findAnagrams("cbaebabacd", "abc")) ;
}

入力

"cbaebabacd"
"abc"

出力

[0, 6]

このように、スライディングウィンドウとマップを活用することで、文字列内のすべてのアナグラムの開始位置を効率よく見つけることができます。