문자열 S가 있다고 가정합니다. 어떤 문자열과 그 자체를 연결하여 쓸 수 있는 S의 비어 있지 않은 고유한 부분 문자열의 수를 찾아야 합니다.
따라서 입력이 "elloelloello"와 같으면 "ello", "lloe", "loel", "oell"과 같은 일부 하위 문자열이 있으므로 출력은 5가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
소수 :=31
-
m :=1^9 + 7
-
fastPow() 함수를 정의하면 기본, 전력,
-
해상도 :=1
-
power> 0일 때 −
-
power &1이 0이 아닌 경우 -
-
res :=res * base
-
res :=res mod m
-
-
기본 :=기본 * 기본
-
기본 :=기본 모드 m
-
전력 =전력 / 2
-
-
반환 해상도
-
createHashValue() 함수를 정의하면 s, n,
가 필요합니다. -
결과 :=0
-
initialize i :=0의 경우, i
-
결과 :=결과 + (s[i] * fastPow(프라임, i))
-
결과 :=결과 모드 m
-
-
반환 결과
-
recalculateHash() 함수를 정의하면 old, newC, oldHash, patLength,
가 사용됩니다. -
newHash :=oldHash - 이전
-
newHash :=newHash * fastPow(프라임, m - 2)
-
newHash :=newHash + (newC * fastPow(prime, patLength - 1))
-
newHash :=newHash 모드 m
-
newHash 반환
-
주요 방법에서 다음을 수행하십시오 -
-
n :=텍스트 크기
-
한 세트를 다음과 같이 정의합니다.
-
initialize i :=2의 경우 i <=n일 때 i :=i + 2를 업데이트하면 −
를 수행합니다.-
temp :=빈 문자열
-
initialize j :=0의 경우 j
-
임시 :=임시 + 텍스트[j]
-
-
hash1 :=createHashValue(temp, i / 2)
-
temp :=빈 문자열)
-
initialize j :=i / 2의 경우 j
-
임시 :=임시 + 텍스트[j]
-
-
hash2 :=createHashValue(temp, i / 2)
-
초기화 s1 :=0, e1 :=i / 2, s2 :=i / 2, e2 :=i, e2
-
hash1이 hash2와 같으면
-
ans
에 hash1 삽입
-
-
hash1 :=recalculateHash(텍스트[s1], 텍스트[e1], 해시1, i / 2)
-
hash2 :=recalculateHash(텍스트[s2], 텍스트[e2], 해시2, i / 2)
-
-
hash1이 hash2와 같으면
-
ans
에 hash1 삽입
-
-
-
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