資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告