Longest Repeating Substring ใน C++

ปัญหา

ให้ String S หาความยาว Substring ที่ซ้ำกัน (ปรากฏมากกว่า 1 ครั้ง) ยาวที่สุด คืน 0 ถ้าไม่มี

ตัวอย่าง: "abbaba" → "ab" หรือ "ba" ความยาว 2

อัลกอริทึม: Dynamic Programming

DP[i][j] = ความยาว Common Suffix ของ S[0..i-1] และ S[0..j-1] ที่จบที่ i-1, j-1

if S[i-1] == S[j-1]: DP[i][j] = DP[i-1][j-1] + 1
else: DP[i][j] = 0

คำตอบ = Max ของ DP[i][j] สำหรับทุก i < j

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int longestRepeatingSubstring(string S) {
        int n = S.size();
        S = " " + S; // 1-based
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        int ans = 0;
        
        for (int i = 1; i <= n; i++) {
            for (int j = i + 1; j <= n; j++) { // j > i ป้องกันนับซ้ำและ overlap
                if (S[i] == S[j]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    ans = max(ans, dp[i][j]);
                }
            }
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.longestRepeatingSubstring("abbaba") << endl; // 2
    cout << ob.longestRepeatingSubstring("abcd") << endl;    // 0
    cout << ob.longestRepeatingSubstring("aaaaa") << endl;   // 4
    return 0;
}

ผลลัพธ์

2
0
4

การเพิ่มประสิทธิภาพ (Space O(N))

ใช้ 1D Array + Iterate j จากท้ายไปหน้า

vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; i++) {
    for (int j = n; j > i; j--) { // ใส่ถอยหลัง
        if (S[i] == S[j]) dp[j] = dp[j-1] + 1;
        else dp[j] = 0;
        ans = max(ans, dp[j]);
    }
}

วิธีที่ดีกว่า: Binary Search + Rolling Hash (Rabin-Karp)

Time: O(N log N) - ใช้ Binary Search ความยาว + Hash ตรวจสอบซ้ำ