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