Chuỗi con trùng lặp dài nhất trong C++

Cho một chuỗi S, xem xét tất cả các chuỗi con liên tiếp trùng lặp xuất hiện ít nhất 2 lần (có thể chồng chéo). Ta cần tìm chuỗi con trùng lặp có độ dài lớn nhất. Nếu không có, trả về chuỗi rỗng. Kết quả có thể rất lớn, trả về modulo 10^9 + 7.

Ví dụ: S = "ababbaba", kết quả là "bab".

Giải thuật

1. Sử dụng tìm kiếm nhị phân trên độ dài chuỗi con (low = 0, high = n-1).
2. Với mỗi độ dài mid, dùng hàm ok(mid, S) kiểm tra xem có chuỗi con trùng lặp độ dài mid không.
3. Hàm ok sử dụng rolling hash (hash đa thức cơ số 26) để tính hash của các chuỗi con độ dài x. Lưu vị trí xuất hiện của mỗi hash trong unordered_map.
4. Khi gặp hash trùng, so sánh trực tiếp chuỗi con để tránh va chạm hash.
5. Nếu tìm thấy, trả về chuỗi con đó; ngược lại trả về rỗng.
6. Cập nhật kết quả ret nếu tìm thấy chuỗi dài hơn.

Ví dụ mã C++

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
    int m = 1e9 + 7;
    int add(lli a, lli b){ return ((a % m) + (b % m)) % m; }
    int sub(lli a, lli b){ return ((a % m) - (b % m) + m) % m; }
    int mul(lli a, lli b){ return ((a % m) * (b % m)) % m; }
    vector<int> power;
    string ok(int x, string s){
        if (x == 0) return "";
        unordered_map<int, vector<int> > hash;
        lli current = 0;
        for (int i = 0; i < x; i++) current = add(mul(current, 26), s[i] - 'a');
        hash[current] = vector<int>(1, 0);
        int n = s.size();
        for (int i = x; i < n; i++) {
            current = sub(current, mul(power[x - 1], s[i - x] - 'a'));
            current = add(mul(current, 26), s[i] - 'a');
            if (hash.count(current)) {
                for (auto& it : hash[current]) {
                    if (s.substr(it, x) == s.substr(i - x + 1, x))
                        return s.substr(it, x);
                }
            } else {
                hash[current].push_back(i - x + 1);
            }
        }
        return "";
    }
    string longestDupSubstring(string S){
        string ret = "";
        int n = S.size();
        power = vector<int>(n, 1);
        for (int i = 1; i < n; i++) power[i] = mul(power[i - 1], 26);
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            string temp = ok(mid, S);
            if (temp.size() == 0) high = mid - 1;
            else {
                if (temp.size() > ret.size()) ret = temp;
                low = mid + 1;
            }
        }
        return ret;
    }
};
int main(){
    Solution ob;
    cout << (ob.longestDupSubstring("ababbaba"));
}

Đầu vào

"ababbaba"

Đầu ra

bab