13713번: 문자열과 쿼리 - Z

Z 기본 문제.

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tll;

const int MAXN = 1000001;
string S, T;
int N, M;
int Z[MAXN]; //Z[i] : S와 S[i...N-1]와의 공통 접두사의 길이
int F[MAXN];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> S;
	N = S.size();
	for(int i=N-1; i>=0; i--) T += S[i]; //구하고자 하는 답은 문자열을 뒤집은 답의 Z 배열이다.
	
	int l = 0, r = 0; //최대 공통 접두사의 구간
	Z[0] = N; //S와 S[0...N-1]은 같은 문자열이다.
	for(int i=1; i<N; i++)
	{
    	//S와 S[i...N-1]와 겹치는 구간을 전처리한다.
        //i > r이면 정보가 없으므로 Z[i] = 0으로 전처리한다.
        //i <= r이면 i가 구간 [l, r]에 포함된다. 따라서 [i, r]의 구간 길이, Z[i-l]을 비교한다.
	    Z[i] = (i > r) ? 0 : min(r-i+1, Z[i-l]);
        
        //겹치는 구간을 전처리한 후, 직접 문자를 하나하나 비교한다.
	    while(i+Z[i] < N && T[Z[i]] == T[i+Z[i]]) Z[i]++;
        
        //S[i+Z[i]-1]는 현재 구한 공통 접두사의 경계이므로, 이 경계가 r보다 크면 구간을 갱신한다.
	    if(i+Z[i]-1 > r) l = i, r = i+Z[i]-1;
	}
	
	cin >> M;
	while(M--)
	{
	    int i; cin >> i;
	    cout << Z[N-i] << "\n";
	}
}