(1605) 반복 부분문자열

https://www.acmicpc.net/problem/1605

단계별로 풀어보기

60단계(문자열 알고리즘 2) 6번째

 

 

 

어떤 두 부분문자열의 LCP가 x라면 길이 x의 반복문자열이 있다는 것이다. 따라서 모든 LCP 중 최대값을 구하면 된다.

이때 떨어져 있는 두 접미사의 LCP는 그 사이에 존재하는 인접한 접미사의 LCP값들 중 최소값과 일치한다는 LCP 정리에 의해 모든 LCP를 구할 필요 없이 접미사 배열에서 구한 LCP 배열의 최대값이 LCP 중 최대값이 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
  int n;
  string s;

  cin >> n >> s;
  
  if(n==1){
    cout << 0;
    
    return 0;
  }

  int d= 1, n2= max(27, n+1);
  vector<int> sfx(n), cnt(n2), idx(n), g(n), tg(n), lcp(n);

  for(int i=0;i<n;i++){
    sfx[i]= i;
    g[i]= s[i]-'a'+1;
  }
  
  while(1){
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[i+d<n?g[i+d]:0]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  idx[--cnt[i+d<n?g[i+d]:0]]= i;
    
    fill_n(cnt.begin(), n2, 0);
    for(int i=0;i<n;i++)  cnt[g[i]]++;
    for(int i=1;i<n2;i++)  cnt[i]+= cnt[i-1];
    for(int i=n-1;i>=0;i--)  sfx[--cnt[g[idx[i]]]]= idx[i];

    tg[sfx[0]]= 1;
    for(int i=1;i<n;i++){
      int curr= sfx[i], prev= sfx[i-1];
      
      bool same= g[curr]==g[prev] && ((curr+d<n?g[curr+d]:0) == (prev+d<n?g[prev+d]:0));
      
      tg[curr]= tg[prev]+!same;
    }

    g= tg;

    if(g[sfx[n-1]]==n)  break;
    d<<= 1;
  }

  s+= ' ';
  
  for(int i=0,k=0;i<n;i++){
    if(g[i]-1){
      int j= sfx[g[i]-2];

      while(s[j+k]==s[i+k])  k++;

      lcp[g[i]-1]= k;
      k=max(k-1,0);
    }
  }

  cout << *max_element(lcp.begin()+1, lcp.end());
  
  return 0;
}