数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
