สตริงซ้ำที่ยาวที่สุดใน C++

คำอธิบายปัญหา

ให้สตริง S พิจารณาสตริงย่อยติดต่อกันที่ซ้ำกัน 2 ครั้งขึ้นไป (อาจทับซ้อนได้) หาสตริงซ้ำที่มีความยาวมากที่สุด หากไม่มีให้คืนสตริงว่าง ผลลัพธ์อาจใหญ่มาก ให้คืนค่า modulo 10⁹+7

ตัวอย่าง

Input: "ababbaba" → Output: "bab"

แนวทางแก้ปัญหา

ใช้ Binary Search ความยาวคำตอบ ร่วมกับ Rolling Hash (Rabin-Karp) เพื่อตรวจสอบว่ามีสตริงย่อยซ้ำความยาว x หรือไม่

1. เตรียมกำลังของ 26 modulo 10⁹+7
2. ฟังก์ชัน ok(x, s): ตรวจสอบว่ามีสตริงย่อยซ้ำความยาว x หรือไม่
   • คำนวณแฮชของสตริงย่อยแรกความยาว x
   • เลื่อนหน้าต่าง (sliding window) คำนวณแฮชแบบ rolling
   • ใช้ unordered_map เก็บตำแหน่งที่เจอแฮชซ้ำ
   • เมื่อเจอแฮชซ้ำ ตรวจสอบสตริงจริงเพื่อป้องกัน collision
3. Binary search ความยาวจาก 0 ถึง n-1

โครงสร้างข้อมูลหลัก

• power[i] = 26ⁱ mod MOD
• hash map: key = hash value, value = vector ของตำแหน่งเริ่มต้น
• ฟังก์ชันช่วย: add, sub, mul สำหรับ modular arithmetic

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int MOD = 1e9 + 7;

class Solution {
    vector<int> power;
    int add(lli a, lli b) { return ((a%MOD)+(b%MOD))%MOD; }
    int sub(lli a, lli b) { return ((a%MOD)-(b%MOD)+MOD)%MOD; }
    int mul(lli a, lli b) { return ((a%MOD)*(b%MOD))%MOD; }
    
    string ok(int x, string& s) {
        if(x == 0) return "";
        unordered_map<int, vector<int>> hash;
        lli cur = 0;
        for(int i=0; i<x; i++) cur = add(mul(cur,26), s[i]-'a');
        hash[cur] = {0};
        int n = s.size();
        for(int i=x; i<n; i++) {
            cur = sub(cur, mul(power[x-1], s[i-x]-'a'));
            cur = add(mul(cur,26), s[i]-'a');
            if(hash.count(cur)) {
                for(int pos : hash[cur]) {
                    if(s.substr(pos, x) == s.substr(i-x+1, x))
                        return s.substr(pos, x);
                }
            } else {
                hash[cur].push_back(i-x+1);
            }
        }
        return "";
    }
    
public:
    string longestDupSubstring(string S) {
        string ret = "";
        int n = S.size();
        power.assign(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.empty()) high = mid-1;
            else {
                if(temp.size() > ret.size()) ret = temp;
                low = mid+1;
            }
        }
        return ret;
    }
};

ความซับซ้อน

• เวลา: O(n log n) โดยเฉลี่ย
• พื้นที่: O(n)