【C言語】アナグラム部分文字列検索プログラムの実装方法

この記事では、長さnのテキスト文字列と長さmのパターン文字列が与えられたとき、テキスト中にパターン本体およびそのすべての順列(アナグラム)が出現する位置を見つける「アナグラム部分文字列検索」のプログラムをC言語で実装する方法を解説します。

問題の概要

与えられたテキストの中から、パターンそのものだけでなく、パターンを構成する文字を並べ替えた文字列(アナグラム)も含めて、すべての出現位置を検出するのが課題です。

入力例

text = "xyztrwqyzxfg" pattern = "xyz"

出力例

Found at index 0
Found at index 7

この例では、テキストの0番目にある"xyz"と、7番目にある"yzx"(xyzのアナグラム)が該当しています。

アルゴリズムの考え方

この問題は、文字列検索で有名なRabin-Karpアルゴリズムと似たアプローチで解くことができます。Rabin-Karp法では各文字のASCII値の合計をmod演算で計算して照合しますが、ここではより正確な判定ができる「文字の出現頻度配列」を利用します。

具体的な手順は以下の通りです。

1. サイズ256の配列を2つ用意し、一方にパターンの文字出現頻度、もう一方にテキスト先頭のウィンドウ部分の文字出現頻度を格納します。
2. ウィンドウを1文字ずつスライドさせながら、右端に新しい文字を追加し、左端から外れる文字を減算して頻度配列を更新します。
3. 各位置でパターン側とテキスト側の頻度配列を比較し、完全に一致していればその開始インデックスを出力します。

この手法により、時間計算量はO(n × 256)、すなわち実質的にO(n)となり、非常に効率的に検索が行えます。

C言語による実装コード

#include <cstring>
#include <iostream>
#define MAX 256
using namespace std;
bool matchPattern(char arr1[], char arr2[]){
   for (int i = 0; i < MAX; i++)
   if (arr1[i] != arr2[i])
      return false;
   return true;
}
void anagramSearch(char* pattern, char* text){
   int M = strlen(pattern);
   int N = strlen(text);
   char patternArray[MAX] = { 0 }, textArray[MAX] = { 0 };
   for (int i = 0; i < M; i++) {
      (patternArray[pattern[i]])++;
      (textArray[text[i]])++;
   }
   for (int i = M; i < N; i++) {
      if (matchPattern(patternArray, textArray))
         printf("\nPattern found at index value : %d", (i-M));
      (textArray[text[i]])++;
      textArray[text[i - M]]--;
   }
   if (matchPattern(patternArray, textArray))
   printf("\nPattern found at index value: %d", (N-M));
}
int main() {
   char text[] = "xyztrwqyzxfg";
   char pattern[] = "xyz";
   printf("Searching Anagram pattern in the string ");
   anagramSearch(pattern, text);
   return 0;
}

実行結果

Searching Anagram pattern in the string
Pattern found at index value: 0
Pattern found at index value: 7

コードのポイント

• matchPattern関数: 2つの頻度配列の全要素を比較し、一致すればtrueを返します。
• 初期化処理: パターン全体とテキストの先頭m文字分の頻度をあらかじめカウントしておきます。
• スライディングウィンドウ: ループ内で右端の文字を加算し、左端の文字を減算することで、毎回頻度を再計算せずにO(1)で更新できます。
• 最後のウィンドウ: ループ終了後、テキスト末尾のウィンドウに対しても照合を行うのを忘れないようにしましょう。

まとめ

文字の出現頻度配列とスライディングウィンドウを組み合わせることで、テキスト中のパターンおよびそのアナグラムを線形時間で効率的に検索できます。Rabin-Karp法のようなハッシュ衝突の心配もなく、確実な判定が可能な実用的な手法です。