Các chuỗi con echo riêng biệt trong C++

Cho chuỗi S, tìm số chuỗi con không rỗng riêng biệt có thể viết dưới dạng nối chuỗi nào đó với chính nó (xx).

Ví dụ: "elloelloello" → 5. Các chuỗi con: "ello", "lloe", "loel", "oell".

Giải pháp

Sử dụng Rolling Hash (Rabin-Karp) để kiểm tra chuỗi con echo:

• Duyệt độ dài chẵn i từ 2 đến n
• Với mỗi i, tính hash của nửa đầu và nửa sau của cửa sổ trượt độ dài i
• Sử dụng hash rolling để cập nhật O(1) khi trượt cửa sổ
• Nếu hash1 == hash2: thêm vào set kết quả
• Trả về kích thước set

Chi tiết: prime=31, mod=1e9+7. Hàm fastPow, createHashValue, recalculateHash cho rolling hash.

Ví dụ mã C++

#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 = 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(); 
    } 
}; 

int main() { 
    Solution ob; 
    cout << (ob.distinctEchoSubstrings("elloelloello")); 
    return 0; 
}

Đầu vào

"elloelloello"

Đầu ra

5