Chuỗi con lặp lại dài nhất trong C ++

Giả sử chúng ta có một chuỗi S, chúng ta phải tìm độ dài của (các) chuỗi con lặp lại dài nhất. Chúng ta sẽ trả về 0 nếu không có chuỗi con lặp lại nào. Vì vậy, nếu chuỗi giống như "abbaba", thì đầu ra sẽ là 2. Vì chuỗi con lặp lại dài nhất là "ab" hoặc "ba".

Trả lại tất cả các từ có thể được tạo theo cách này, theo thứ tự từ vựng.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

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

• đặt S:=một khoảng trống được nối với S

• đặt ret:=0

• tạo một ma trận dp có kích thước (n + 1) x (n + 1)

• cho tôi trong phạm vi từ 1 đến n

  • cho j trong phạm vi 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ả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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"

Đầu ra

2