BOJ(백준) 14417번 팰린드롬과 쿼리2

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

14417번: 팰린드롬과 쿼리 2

쿼리에서 체크해야 될 펠린드롬의 조건은 다음과 같다

① S의 index번째에서 시작할 것

② 길이가 적어도 len일 것

 

쿼리에서 입력받는 index를 i, 길이를 L이라고 할 때 

 

조건 ①은 i<=k인 인덱스 k중에서 최장 펠린드롬이 자신을 포함하고 있는 것의 개수를 세면 된다.

조건 ②는 위의 조건을 만족하는 인덱스 k가 (i+L-1)<=k여야 한다는 뜻이다.

 

문제의 예시 입력으로 해결 방법을 알아보자 아래 표의 첫 번째 줄은 인덱스, 두 번째는 인덱스에 해당하는 문자, 세 번째는 해당 인덱스를 중심으로 하는 최장 펠린드롬의 반지름이다. (여기서는 펠린드롬의 반지름을 (전체 길이+1)/2이라고 하자)

1	2	3	4	5
a	b	a	b	a
1	2	3	2	1

 

i와 k의 차이가 1커질 때마다 요구되는 k의 반지름 길이가 1이 늘어나므로 이를 사전에 처리하기 위해 각각의 반지름에 인덱스만큼 빼주면 표는 다음과 같이 된다.

1	2	3	4	5
a	b	a	b	a
0	0	0	-2	-4

 

표를 다시 살펴보면 각 값들이 -i보다 크다면 해당 인덱스의 반지름이 i에 닿는다는 것을 알 수 있다.

 

따라서 최종적으로 우리가 구해야 될 것은 (i+L-1)<=k인 인덱스 k중에서 값이 -i보다 큰 것을 개수이다.

문자열의 길이가 최대 10만이고 쿼리의 수도 10만이므로 각각의 쿼리를 O(logN)에 처리해야 되는데 쿼리에 업데이트가 없으므로 머지 소트 트리를 사용하기 매우 좋은 상황이다.

 

추가로 문자열의 길이가 최대 10만이므로 각 인덱스의 최장 펠린드롬을 구할 때 매내처 알고리즘을 사용해야 된다.

 

매내처 알고리즘에 대한 간단한 설명은 아래에 존재한다.

https://4luv1015.tistory.com/6

BOJ 25582번 pqbd

 

AC code

#include <bits/stdc++.h>

using namespace std;
int arr[200001],s2[200001],p,r,N,M,t1,t2;
vector<vector<int>> tree;

vector<int> &init(int node,int start,int end)
{
	if(start==end) return tree[node]={arr[start]};
	int mid=(start+end)/2;
	vector<int> &left=init(node*2,start,mid),&right=init(node*2+1,mid+1,end);
	tree[node].resize(left.size()+right.size());
	merge(left.begin(),left.end(),right.begin(),right.end(),tree[node].begin());
	return tree[node];
}

int query(int node,int start,int end,int left,int right,int val)
{
	if(right<start||left>end)return 0;
	if(left<=start&&right>=end)return tree[node].size()-(upper_bound(tree[node].begin(),tree[node].end(),val)-tree[node].begin());
	int mid=(start+end)/2;
	return query(node*2,start,mid,left,right,val)+query(node*2+1,mid+1,end,left,right,val);
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	string s1;
	cin>>s1;
	int len=s1.length();
	for(int i=0;i<len;i++) s2[2*i+1]=s1[i];
	for(int i=0;i<2*len+1;i++) {
		if(i<=r) arr[i]=min(r-i,arr[2*p-i]);
		while(s2[i-arr[i]-1]==s2[i+arr[i]+1]&&i-arr[i]-1>=0&&i+arr[i]+1<2*len+1) arr[i]++;
		if(i+arr[i]>r) {
			r=i+arr[i];
			p=i;
		}
	}
	for(int i=1;i<2*len;i+=2) {
		arr[i]=(1+arr[i])/2-((i+1)/2);
		arr[i+1]=arr[i+1]/2-((i+1)/2);
	}
	N=2*len-1;
	tree.resize(4*N+1);
	init(1,1,N);
	cin>>M;
	while(M--)
	{
		cin>>t1>>t2;
		t1++;
		int tmp=query(1,1,N,t2?(t1*2+t2-2):(t1*2-1),N,-t1);
		if(!t2)tmp++;
		cout<<tmp<<"\n";
	}
}

 

매내처 알고리즘의 특성상 원본 문자열을 변형시켜야 되다 보니 쿼리를 처리에서 계산이 조금 난잡해졌다.

또한 len이 0인 경우(len이 1일때의 정답+1이 정답)가 존재하다보니 추가로 예외 처리를 해야됐다.