資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中不同的回聲子字串
假設我們有一個字串 S；我們必須找到 S 的不同非空子字串的數量，這些子字串可以寫成某個字串與其自身的連線。
因此，如果輸入類似於“elloelloello”，則輸出將為 5，因為存在一些子字串，例如“ello”、“lloe”、“loel”、“oell”。
為了解決這個問題，我們將遵循以下步驟 -
prime := 31
m := 1^9 + 7
定義一個函式 fastPow()，它將接收底數、冪，
res := 1
當 power > 0 時，執行 -
如果 power & 1 不為零，則 -
res := res * base
res := res mod m
base := base * base
base := base mod m
power = power / 2
返回 res
定義一個函式 createHashValue()，它將接收 s、n，
result := 0
初始化 i := 0，當 i < n 時，更新 (i 增加 1)，執行 -
result := result + (s[i] * fastPow(prime, i))
result := result mod m
返回 result
定義一個函式 recalculateHash()，它將接收 old、newC、oldHash、patLength，
newHash := oldHash - old
newHash := newHash * fastPow(prime, m - 2)
newHash := newHash + (newC * fastPow(prime, patLength - 1))
newHash := newHash mod m
返回 newHash
從主方法執行以下操作 -
n := 文字的大小
定義一個集合 ans
初始化 i := 2，當 i <= n 時，更新 i := i + 2，執行 -
temp := 空字串
初始化 j := 0，當 j < i / 2 時，更新 (j 增加 1)，執行 -
temp := temp + text[j]
hash1 := createHashValue(temp, i / 2)
temp := 空字串)
初始化 j := i / 2，當 j < i 時，更新 (j 增加 1)，執行 -
temp := temp + text[j]
hash2 := createHashValue(temp, i / 2)
初始化 s1 := 0，e1 := i / 2，s2 := i / 2，e2 := i，當 e2 < n 時，更新 (s1、s2、e1、e2 增加 1)，執行 -
如果 hash1 等於 hash2，則
將 hash1 插入 ans
hash1 := recalculateHash(text[s1], text[e1], hash1, i / 2)
hash2 := recalculateHash(text[s2], text[e2], hash2, i / 2)
如果 hash1 等於 hash2，則
將 hash1 插入 ans
返回 ans 的大小
讓我們看看以下實現以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const lli prime = 31;
const lli m = 1e9 + 7;
class Solution {
public:
lli fastPow(lli base, lli power){
lli res = 1;
while (power > 0) {
if (power & 1) {
res = res * base;
res %= m;
}
base *= base;
base %= m;
power >>= 1;
}
return res;
}
lli createHashValue(string s, lli n){
lli result = 0;
for (lli i = 0; i < n; i++) {
result += (lli)(s[i] * fastPow(prime, i));
result %= m;
}
return result;
}
lli recalculateHash(char old, char newC, lli oldHash, lli
patLength){
lli newHash;
newHash = oldHash - (lli)old;
newHash *= fastPow(prime, m - 2);
newHash += ((lli)newC * fastPow(prime, patLength - 1));
newHash %= m;
return newHash;
}
int distinctEchoSubstrings(string text){
int n = text.size();
set<int> ans;
for (int i = 2; i <= n; i += 2) {
string temp = "";
for (int j = 0; j < i / 2; j++) {
temp += text[j];
}
int hash1 = createHashValue(temp, i / 2);
temp = "";
for (int j = i / 2; j < i; j++) {
temp += text[j];
}
int hash2 = createHashValue(temp, i / 2);
for (int s1 = 0, e1 = i / 2, s2 = i / 2, e2 = i; e2 < n;
s1++, s2++, e1++, e2++) {
if (hash1 == hash2) {
ans.insert(hash1);
}
hash1 = recalculateHash(text[s1], text[e1], hash1,
i / 2);
hash2 = recalculateHash(text[s2], text[e2], hash2,
i / 2);
}
if (hash1 == hash2) {
ans.insert(hash1);
}
}
return ans.size();
}
};
main(){
Solution ob;
cout << (ob.distinctEchoSubstrings("elloelloello"));
}輸入
"elloelloello"
輸出
5
105 次檢視
