C++에서 가장 긴 반복 부분 문자열

<시간/>

문자열 S가 있다고 가정하고 가장 긴 반복 부분 문자열의 길이를 찾아야 합니다. 반복되는 하위 문자열이 없으면 0을 반환합니다. 따라서 문자열이 "abbaba"와 같으면 출력은 2가 됩니다. 가장 오래 반복되는 하위 문자열은 "ab" 또는 "ba"입니다.

이러한 방식으로 형성할 수 있는 모든 단어를 사전순으로 반환합니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=S
의 크기
set S :=S로 연결된 하나의 공백
설정 ret :=0
(n + 1) x (n + 1) 크기의 행렬 dp 하나 생성
범위 1에서 n까지의 i에 대해
- 범위 i + 1에서 n
  의 j에 대해
  - S[i] =S[j]
    인 경우
    - dp[i, j] :=dp[i, j] 및 1 + dp[i – 1, j – 1]의 최대값
    - ret :=ret 및 dp[i, j]의 최대값
리턴 렛

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#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"));
}

입력

"abbaba"