数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装学
法学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
更新于：2020年8月5日
181 次浏览
广告