(11479) 서로 다른 부분 문자열의 개수 2

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

단계별로 풀어보기

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

 

 

 

어떤 LCP의 값이 x라면 길이 x인 똑같은 부분문자열이 있다는 의미고, 이는 곧 해당 부분문자열의 부분문자열인 길이 x-1, x-2, ..., 1의 똑같은 부분문자열도 있다는 의미다. 따라서 모든 부분문자열의 수에서 LCP 배열의 총합을 빼주면 된다.

 

 

 

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

int main() {
  string s;

  cin >> s;

  int n= s.length(), 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);
    }
  }

  long ans= 1L*n*(n+1)/2;
  for(int i=1;i<n;i++)  ans-= lcp[i];
  
  cout << ans;
  
  return 0;
}