Giả sử chúng ta có một chuỗi S; chúng ta phải tìm số lượng các chuỗi con khác biệt không rỗng của S có thể được viết dưới dạng nối của một số chuỗi với chính nó.
Vì vậy, nếu đầu vào là "elloelloello", thì đầu ra sẽ là 5, vì có một số chuỗi con như "ello", "lloe", "loel", "oell".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
số nguyên tố:=31
-
m:=1 ^ 9 + 7
-
Xác định một hàm fastPow (), hàm này sẽ lấy base, power,
-
res:=1
-
trong khi quyền lực> 0, thực hiện -
-
nếu power &1 khác 0 thì -
-
res:=res * base
-
res:=res mod m
-
-
base:=base * base
-
base:=base mod m
-
power =power / 2
-
-
trả lại res
-
Xác định một hàm createHashValue (), hàm này sẽ nhận s, n,
-
kết quả:=0
-
để khởi tạo i:=0, khi i
-
result:=result + (s [i] * fastPow (prime, i))
-
result:=kết quả mod m
-
-
trả về kết quả
-
Xác định một hàm recalculateHash (), hàm này sẽ lấy old, newC, oldHash, patLength,
-
newHash:=oldHash - old
-
newHash:=newHash * fastPow (prime, m - 2)
-
newHash:=newHash + (newC * fastPow (prime, patLength - 1))
-
newHash:=newHash mod m
-
trả lại newHash
-
Từ phương thức chính, hãy làm như sau -
-
n:=kích thước của văn bản
-
Xác định một bộ ans
-
để khởi tạo i:=2, khi i <=n, hãy cập nhật i:=i + 2, do -
-
temp:=chuỗi trống
-
để khởi tạo j:=0, khi j
-
temp:=temp + text [j]
-
-
hash1:=createHashValue (tạm thời, i / 2)
-
temp:=chuỗi trống)
-
để khởi tạo j:=i / 2, khi j
-
temp:=temp + text [j]
-
-
hash2:=createHashValue (tạm thời, i / 2)
-
để khởi tạo s1:=0, e1:=i / 2, s2:=i / 2, e2:=i, khi e2
-
nếu hash1 giống với hash2 thì
-
chèn hash1 vào ans
-
-
hash1:=recalculateHash (text [s1], text [e1], hash1, i / 2)
-
hash2:=recalculateHash (text [s2], text [e2], hash2, i / 2)
-
-
nếu hash1 giống với hash2 thì
-
chèn hash1 vào ans
-
-
-
kích thước trả về của ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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"));
} Đầu vào
"elloelloello"
Đầu ra
5