C ++中不同的Echo子字符串
假设我们有一个字符串S；我们必须找到S的不同非空子字符串的数量，这些数量可以写为某个字符串与其自身的串联。
因此，如果输入类似于“elloelloello”，则输出将为5，因为存在一些子字符串，如“ello”，“lloe”，“loel”，“oell”。
为了解决这个问题，我们将遵循以下步骤-
素数：=31
m：=1^9+7
定义一个功能fastPow()，这将需要基础，力量，
res：=1
当幂>0时，执行-
res：=res*基数
res：=resmodm
如果power＆1不为零，则-
基本：=基本*基本
base：=基本modm
幂=幂/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：=newHashmodm
返回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