在这个问题中,我们得到了字符串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