C++でのすべてのサフィックスを持つ文字列の類似性の合計

この問題では、文字列strが与えられます。私たちのタスクは、文字列とそのすべてのサフィックスの類似性の合計を見つけるプログラムを作成することです。

文字列strのサフィックスは、文字列の開始文字を削除して作成されたすべての文字列です。

文字列の類似点 str1とstr2は、両方の文字列に共通する最長のプレフィックスの長さです。たとえば、str1 =‘abbac’およびstr2 =‘abb’は3です。

str1 =‘abca’およびstr2 =‘ca’は0です。最初から数えます。

問題を理解するために例を見てみましょう

入力 − str =‘xyxyx’

出力 −

説明 −すべての部分文字列とすべての接尾辞を持つ文字列の類似点は-

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

この問題を解決するために、Zアルゴリズムを使用してZ配列を計算します。 Z配列は、文字列の長さに等しい長さの配列です。すべての要素はstrのプレフィックスを格納します。以下のプログラムは実装を示しています

例

#include <bits/stdc++.h>
using namespace std;
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