(16229) 반복 패턴

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

단계별로 풀어보기

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

 

 

 

Z배열을 구한 뒤 어떤 i에 대해 z[i]+i가 문자열의 길이와 같다고 하자. 이 경우 이 문자열은 길이 i짜리 패턴이 반복되다가 끝부분이 잘린(안 잘렸을 수도 있음) 형태가 된다. 이때 추가로 덧붙여야 하는 문자가 K글자 이하인지 확인하여 맞다면 정답 변수와 비교해 큰 값으로 갱신해주면 된다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n, k;
  string s;

  cin >> n >> k >> s;

  if(k>=n){
    cout << n;
    
    return 0;
  }
  
  int x= (n-1)/2, l= 0, r= 0, ans= 0;
  vector<int> z(s.length());
  z[0]= n;
  
  for(int i=1;i<n;i++){
    if(i>r){
      l= i;
      r= i;
      while(r<n && s[r]==s[r-l])  r++;
      z[i]= r-l;
      r--;
    }else{
      if(z[i-l]<=r-i){
        z[i]= z[i-l];
      }else{
        l= i;
        while(r<n && s[r]==s[r-l])  r++;
        z[i]= r-l;
        r--;
      }
    }

    if(z[i]+i==n && (n%i==0 || i-n%i<=k)){
      
      ans= i;
    }
  }

  cout << ans;

  return 0;
}