(13713) 문자열과 쿼리

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

단계별로 풀어보기

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

 

 

 

Z-array란 어떤 문자열 S와 부분문자열 S[i:]에 대해 최장 접두사의 길이를 Z[i]의 값으로 갖는 배열을 의미한다. Z 알고리즘은 이 Z-array를 선형 시간에 구하는 알고리즘이다. 매내처, KMP처럼 이전에 탐색한 정보를 이용하는 알고리즘인데, Z[i]=x라고 한다면 i+x-1번째 문자열까지는 우리가 탐색이 끝났다는 소리다. 따라서 i+1~i+x-1번째 문자열에서 Z배열을 구할 때 이 결과를 재사용할 수 있다.

단 이 문제에서는 접두사가 아니라 접미사를 구해야 하는데, 문자열을 뒤집어서 Z알고리즘을 쓰면 된다.

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  string s;
  
  cin >> s;
  
  reverse(s.begin(), s.end());
  
  int l= 0, r= 0, n= s.length(), m;
  vector<int> z(s.length());
  z[0]= n;
  
  for(int k=1;k<n;k++){
    if(k>r){
      l= k;
      r= k;
      while(r<n && s[r]==s[r-l])  r++;
      z[k]= r-l;
      r--;
    }else{
      if(z[k-l]<=r-k){
        z[k]= z[k-l];
      }else{
        l= k;
        while(r<n && s[r]==s[r-l])  r++;
        z[k]= r-l;
        r--;
      }
    }
  }

  cin >> m;
  
  while(m--){
    int i;

    cin >> i;

    cout << z[n-i] << "\n";
  }

  return 0;
}