文字列中のアナグラム出現回数をカウントするアルゴリズムとC++・Javaでの実装例

テキストストリーム(文字列)と1つの単語が入力として与えられ、その単語のアナグラムがテキストストリームの中に何回出現するかを求めるのが本記事のテーマです。
アナグラムとは、単語を構成する文字を並べ替えてできる別の単語やフレーズのことを指します。有名な例としては、文「New York Times」のアナグラムとして「Monkeys write」が挙げられます。

具体例

例1

入力: 文字列 = 「workitwrokoffowkr」、単語 = 「work」

出力: 文字列中のアナグラムの出現回数:3

解説: 「work」のアナグラムには work、wrok、rowk、owkr などがあります。与えられた文字列中には work、wrok、owkr の3つが含まれているため、出現回数は3となります。

例2

入力: 文字列 = 「expresshycool」、単語 = 「Zen」

出力: 文字列中のアナグラムの出現回数:0

解説: 「zen」のアナグラムには nez、ezn、enz、zne、nze、zen などがあります。しかし、与えられた文字列中には「zen」のアナグラムが1つも存在しないため、出現回数は0となります。

アルゴリズムの考え方

• 文字列(stream)と単語(w)を関数 countAna(stream, w) に渡して処理を行います。
• countAna 関数内では、まず出現回数を記録するためのカウンタを初期化します。
• i = 0 から i <= stream.length() − w.length() まで FORループを回します。
• ループ内では、単語と、ストリームから取り出した単語と同じ長さの部分文字列 stream.substring(i, i + w.length()) を arrangeAna(w, 部分文字列) に渡します。
• arrangeAna 関数内では、2つの文字列をそれぞれ文字配列に変換してソートします。
• Arrays.equals(c1, c2) によって、ソート済みの部分文字列と単語が一致するかどうか(=アナグラムかどうか)を判定し、true / false を返します。
• 結果が true の場合、countAna 内のカウンタをインクリメントします。
• main メソッドで結果を受け取り、出力します。

この手法のポイントは、「2つの文字列がアナグラムであるなら、文字をソートすると同一の文字列になる」という性質を利用している点です。これにより、すべての並べ替えパターンを生成する非効率な方法を避けることができます。

実装例(Java)

import java.io.*;
import java.util.*;

public class testClass {
   static boolean arrangeAna(String s1, String s2) {
      char[] c1 = s1.toCharArray();
      char[] c2 = s2.toCharArray();
      Arrays.sort(c1);
      Arrays.sort(c2);
      if (Arrays.equals(c1, c2)) {
         return true;
      } else {
         return false;
      }
   }

   static int countAna(String stream, String w) {
      int count = 0;
      for (int i = 0; i <= (stream.length()) - (w.length()); i++) {
         if (arrangeAna(w, stream.substring(i, i + (w.length())))) {
            count++;
         }
      }
      return count;
   }

   public static void main(String args[]) {
      Scanner scan = new Scanner(System.in);
      String stream = scan.next(); // workitwrokoffowkr
      String w = scan.next(); // work
      System.out.print(countAna(stream, w));
   }
}

参考:C++での実装例

同じロジックはC++でも次のように実装できます。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool arrangeAna(string s1, string s2) {
   sort(s1.begin(), s1.end());
   sort(s2.begin(), s2.end());
   return s1 == s2;
}

int countAna(const string& stream, const string& w) {
   int count = 0;
   for (int i = 0; i <= (int)stream.size() - (int)w.size(); i++) {
      if (arrangeAna(w, stream.substr(i, w.size()))) {
         count++;
      }
   }
   return count;
}

int main() {
   string stream, w;
   cin >> stream >> w; // workitwrokoffowkr / work
   cout << countAna(stream, w) << endl;
   return 0;
}

上記のコードを実行すると、次のような出力が得られます。

出力

文字列中のアナグラムの出現回数:3

計算量の目安

テキストストリームの長さを n、単語の長さを m とすると、比較対象の部分文字列は最大 n 通り生成され、それぞれに対してソート(O(m log m))と比較(O(m))が行われるため、全体の時間計算量は O(n・m log m) となります。さらに高速化したい場合は、アルファベット26文字分の出現頻度カウンタを用意し、窓を1文字ずつずらしながら頻度を差分更新する「スライディングウィンドウ」手法を採用することで、O(n) まで削減可能です。