[백준 1701] Cubeditor (C#, C++) - soo:bak

문제 링크

1701번 - Cubeditor

설명

주어진 문자열에서 두 번 이상 등장하는 부분문자열 중 가장 긴 길이를 구하는 문제입니다.

부분문자열은 서로 겹쳐도 됩니다.

접근법

먼저, 문자열의 모든 접미사에 대해 부분 일치 테이블을 계산합니다. 부분 일치 테이블은 각 위치에서 접두사와 접미사가 일치하는 최대 길이를 저장하므로, 이 값이 크다는 것은 같은 패턴이 반복 등장한다는 의미입니다.

다음으로, 각 접미사의 부분 일치 테이블에서 최댓값을 구합니다. 예를 들어 문자열 abcdabcabb에서 접미사 abcabb의 부분 일치 테이블 최댓값은 2인데, 이는 ab가 두 번 등장하기 때문입니다.

이후, 모든 접미사에 대해 구한 최댓값들 중 가장 큰 값이 답이 됩니다. 접미사마다 테이블을 구하면 문자열 내 모든 위치에서 시작하는 반복을 탐색할 수 있습니다.

시간복잡도는 O(n²)이며, 문자열 길이가 5000 이하이므로 충분합니다.

Code

C#

using System;

namespace Solution {
  class Program {
    static int LongestRepeat(string s) {
      var n = s.Length;
      var best = 0;
      for (var start = 0; start < n; start++) {
        var m = n - start;
        var pi = new int[m];
        var j = 0;
        for (var i = 1; i < m; i++) {
          while (j > 0 && s[start + i] != s[start + j])
            j = pi[j - 1];
          if (s[start + i] == s[start + j]) {
            pi[i] = ++j;
            if (pi[i] > best)
              best = pi[i];
          }
        }
      }
      return best;
    }

    static void Main(string[] args) {
      var str = Console.ReadLine()!;
      Console.WriteLine(LongestRepeat(str));
    }
  }
}

C++

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

typedef vector<int> vi;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  cin >> s;
  int n = s.size();
  int ans = 0;

  for (int st = 0; st < n; st++) {
    int m = n - st;
    vi pi(m, 0);
    for (int i = 1, j = 0; i < m; i++) {
      while (j > 0 && s[st + i] != s[st + j])
        j = pi[j - 1];
      if (s[st + i] == s[st + j]) {
        pi[i] = ++j;
        ans = max(ans, pi[i]);
      }
    }
  }

  cout << ans << "\n";

  return 0;
}