文字列Tの中に含まれるSのすべてのアナグラムの開始インデックスを見つけるプログラム（C++・Python解説）

問題の概要

2つの文字列 S と T が与えられたとき、T の中に S のアナグラム（文字の並べ替え）が現れる開始インデックスをすべて求めるという問題です。文字列は小文字の英字のみで構成され、S と T の長さはそれぞれ 20 および 100 を超えないものとします。

たとえば、入力が S = "cab"、T = "bcabxabc" の場合、出力は [0, 1, 5] になります。これは、T の部分文字列として "bca"（インデックス 0）、"cab"（インデックス 1）、"abc"（インデックス 5）がそれぞれ S のアナグラムと一致するためです。

アルゴリズムの流れ

この問題は「スライディングウィンドウ」と呼ばれる手法を使うことで効率的に解けます。手順は以下の通りです。

• マップ m を定義し、n := s のサイズ、left := 0、right := 0、counter := p のサイズで初期化します。
• 結果を格納するための配列 ans を用意します。
• p に含まれる各文字の出現回数をマップ m に記録します。
• right を 0 ～ n-1 の範囲でループします。
  • 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] が存在し、カウントが 0 でなければ、right を 1 減らしてループを抜けます。
  • m に s[left] が存在しない場合は、left := right + 1 と設定します。
• 最後に ans を返します。

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;
    }
};

int main(){
    Solution ob;
    print_vector(ob.findAnagrams("bcabxabc", "cab"));
}

入力

"bcabxabc", "cab"

出力

[0, 1, 5]

Pythonによる実装例

同じ問題は、Python では標準ライブラリの Counter を使ったスライディングウィンドウでより簡潔に記述できます。

from collections import Counter

class Solution:
    def findAnagrams(self, s: str, p: str):
        n, m = len(s), len(p)
        ans = []
        if m > n:
            return ans
        p_count = Counter(p)
        window = Counter(s[:m])
        if window == p_count:
            ans.append(0)
        for i in range(m, n):
            window[s[i]] += 1          # 右端の新しい文字を追加
            window[s[i - m]] -= 1      # 左端の古い文字を削除
            if window[s[i - m]] == 0:
                del window[s[i - m]]
            if window == p_count:
                ans.append(i - m + 1)
        return ans

ob = Solution()
print(ob.findAnagrams("bcabxabc", "cab"))

出力

[0, 1, 5]

まとめ

T のすべての部分文字列を毎回ソートして比較する素朴な方法では計算コストが大きくなりますが、文字の出現頻度を管理しながらウィンドウを少しずつずらしていくことで、無駄な比較を省きながらアナグラムの開始位置をすべて効率的に列挙できます。このテクニックは、部分文字列検索や頻度ベースの照合を行う多くの文字列処理問題にも応用できます。