【C++解説】文字列とそのすべての接尾辞との類似度の合計を求める方法

この問題では、文字列 str が与えられます。求めるのは、元の文字列とそのすべての接尾辞（サフィックス）との類似度の合計です。

接尾辞と類似度とは？

接尾辞とは、文字列の先頭から文字を削除していくことで生成されるすべての文字列のことです。

類似度とは、2つの文字列 str1 と str2 の間で共通する最長接頭辞（プレフィックス）の長さを指します。

• 例1：str1 = ‘abbac’、str2 = ‘abb’ の場合 → 共通接頭辞は ‘abb’ なので類似度は 3
• 例2：str1 = ‘abca’、str2 = ‘ca’ の場合 → 先頭から比較するため共通部分がなく、類似度は 0

問題例で理解しよう

入力： str = ‘xyxyx’

出力： 9

説明： 各接尾辞と元の文字列との類似度は以下の通りです。

‘xyxyx’ -> 5
‘yxyx’  -> 0
‘xyx’   -> 3
‘yx’    -> 0
‘x’     -> 1
合計 = 5 + 0 + 3 + 0 + 1 = 9

解法アプローチ：Zアルゴリズム

この問題を効率的に解くには、Zアルゴリズムを使って Z配列 を計算します。

Z配列は、元の文字列と同じ長さを持つ配列で、各要素には「その位置から始まる部分文字列が、文字列の接頭辞といくつの文字で一致するか」が格納されます。実は、Z配列の各値がまさに「元の文字列と各接尾辞との類似度」に相当するため、それらをすべて足し合わせるだけで答えが得られます。

実装例

#include <bits/stdc++.h>
using namespace std;

// Z配列を生成する関数
void createZArray(string str, int n, int Zarray[]) {
   int L, R, k;
   L = R = 0;
   for (int i = 1; i < n; ++i) {
      if (i > R) {
         L = R = i;
         while (R < n && str[R - L] == str[R])
            R++;
         Zarray[i] = R - L;
         R--;
      }
      else {
         k = i - L;
         if (Zarray[k] < R - i + 1)
         Zarray[i] = Zarray[k];
         else {
            L = i;
            while (R < n && str[R - L] == str[R])
              R++;
            Zarray[i] = R - L;
            R--;
         }
      }
   }
}

// 類似度の合計を計算する関数
int calSumSimilarities(string s, int n) {
   int Zarray[n] = { 0 };
   createZArray(s, n, Zarray);
   int total = n; // 接尾辞「文字列全体」との類似度は文字列長そのもの
   for (int i = 1; i < n; i++)
      total += Zarray[i];
   return total;
}

int main() {
   string s = "xyxyx";
   int n = s.length();
   cout<<"Sum of similarities of string with all of its suffixes is "<<calSumSimilarities(s, n);
   return 0;
}

出力結果

Sum of similarities of string with all of its suffixes is 9

計算量について

Zアルゴリズムの計算量は O(n) です。単純に各接尾辞を先頭から順番に比較する素朴な方法では最悪 O(n²) かかりますが、Zアルゴリズムを利用することで非常に大きな文字列でも高速に処理できます。