假设我们有一个字符串S；我们必须找到S的不同非空子字符串的数量，这些数量可以写为某个字符串与其自身的串联。
因此，如果输入类似于“ elloelloello”，则输出将为5，因为存在一些子字符串，如“ ello”，“ lloe”，“ loel”，“ oell”。
为了解决这个问题，我们将遵循以下步骤-
素数：= 31
m：= 1 ^ 9 + 7
定义一个功能fastPow()，这将需要基础，力量，
res：= 1
当幂> 0时，执行-
res：= res *基数
res：= res mod m
如果power＆1不为零，则-
基本：=基本*基本
base：=基本mod m
幂=幂/ 2
返回资源
定义一个函数createHashValue()，它将取s，n，
结果：= 0
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-
结果：=结果+（s [i] * fastPow(prime,i)）
结果：=结果模数m
返回结果
定义一个函数recalculateHash()，它将使用old，newC，oldHash，patLength，
newHash：= oldHash-旧
newHash：= newHash * fastPow（素数，m-2）
newHash：= newHash +（newC * fastPow(prime,patLength-1)）
newHash：= newHash mod m
返回newHash
从主要方法中执行以下操作-
n：=文字大小
定义一组
对于初始化i：= 2，当i <= n时，更新i：= i + 2，执行-
将hash1插入ans
如果hash1与hash2相同，则
hash1：= recalculateHash（text [s1]，text [e1]，hash1，i / 2）
hash2：= recalculateHash（text [s2]，text [e2]，hash2，i / 2）
将hash1插入ans
temp：= temp +文字[j]
temp：= temp +文字[j]
temp：=空字符串
对于初始化j：= 0，当j <i / 2时，更新（将j增加1），执行-
hash1：= createHashValue（temp，i / 2）
temp：=空字符串）
对于初始化j：= i / 2，当j <i时，更新（将j增加1），执行-
hash2：= createHashValue（temp，i / 2）
对于初始化s1：= 0，e1：= i / 2，s2：= i / 2，e2：= i，当e2 <n时，更新（将s1，s2，e1，e2增加1），-
如果hash1与hash2相同，则
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