Chuỗi con lặp lại dài nhất (Longest Repeating Substring) trong C++

Giả sử ta có chuỗi S, ta phải tìm độ dài của chuỗi con lặp lại dài nhất. Trả về 0 nếu không có chuỗi con lặp lại. Ví dụ, chuỗi "abbaba" cho kết quả 2. Vì chuỗi con lặp lại dài nhất là "ab" hoặc "ba".

Trả về tất cả các từ có thể hình thành theo cách này, theo thứ tự từ điển.

Để giải quyết, ta thực hiện các bước sau:

• n := kích thước S.

• Đặt S := một khoảng trắng nối với S.

• Đặt ret := 0.

• Tạo ma trận dp kích thước (n + 1) x (n + 1).

• Với i từ 1 đến n:

  • Với j từ i + 1 đến n:

    • Nếu S[i] = S[j]:

      • dp[i, j] := max của dp[i, j] và 1 + dp[i - 1, j - 1].

      • ret := max của ret và dp[i, j].

• Trả về ret.

Xem triển khai dưới đây để hiểu rõ hơn:

Ví dụ minh họa

#include <bits/stdc++.h> using namespace std; class Solution {    public:    int longestRepeatingSubstring(string S) {       int n = S.size();       S = " " + S;       int ret = 0;       vector < vector <int> > dp(n + 1, vector <int> (n + 1));       for(int i = 1; i <= n; i++){          for(int j = i + 1; j <= n; j++){             if(S[i] == S[j]){                dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);                ret = max(ret, dp[i][j]);             }          }       }       return ret;    } }; main(){    Solution ob;    cout << (ob.longestRepeatingSubstring("abbaba")); }

Đầu vào

"abbaba"

Kết quả

2