제출 #18117

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18117		comet	회문 (APIO14_palindrome)	C++98	23 / 100	1000 ms	47644 KiB

palindrome

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#include <map>
#include <vector>
using namespace std;
typedef long long ll;
typedef vector<int> vec;
typedef vector<vec> mat;
mat path;
#define pb push_back
#define MOD (ll)(1e9+9)
ll p=209;

int N;
char a[300010],b[600010];

ll d[600010];
ll pk[600010];
ll Hash[600010];

map<ll,ll> ID;
ll sz;

ll cnt[300010],len[300010];

void init(){

	for(int i=0;i<N;i++){
		b[2*i+1]=a[i];
	}

	int n=2*N+1;

	pk[0]=1;
	for(int i=1;i<n;i++){
		pk[i]=(pk[i-1]*p)%MOD;
	}

	ll sum=0;
	for(int i=0;i<n;i++){
		Hash[i]=(sum*p+b[i])%MOD;
		sum=Hash[i];
	}

	ID[0]=sz++;

	for(int i=0;i<N;i++){
		if(ID.find(a[i])==ID.end()){
			ID[a[i]]=sz++;
			len[sz-1]=1;
		}
	}

	for(int i=0;i<N;i++){
		path[0].pb(ID[a[i]]);
	}

}


ll query(int L,int R){
	if(L==0)return Hash[R];
	int dx=R-L+1;
	return (Hash[R]-(Hash[L-1]*pk[dx])%MOD+MOD)%MOD;
}

void output(int L,int R){
	for(int i=L;i<=R;i++){
		printf("%c ",b[i]);
	}
	printf(" : %lld\n",query(L,R));
}

void push(int L,int R){
	if(L%2==0)return;
	// printf("push %d~%d\n",L,R);

	// output(L,R);

	if(ID.find(query(L,R))==ID.end()){
		ID[query(L,R)]=sz++;
		len[ID[query(L,R)]]=(R-L+2)/2;
	}

	// printf("id : %lld\n",ID[query(L,R)]);

	if(L+2==R){
		path[0].pb(ID[query(L,R)]);
	}
	if(L+2<=R-2){
		path[ID[query(L+2,R-2)]].pb(ID[query(L,R)]);
	}

	// printf("len : %lld\n",len[ID[query(L,R)]]);
}

void add(int L,int R){
	if(L%2==0)return;
	// printf("add %d~%d\n",L,R);

	// output(L,R);
	cnt[ID[query(L,R)]]++;

	// printf("cnt : %lld\n",cnt[ID[query(L,R)]]);
}

void manacher(){

	int n=2*N+1,k=0,l,r;
	for(int i=0;i<n;i++){
		if(d[k]+k>i){
			d[i]=min(d[k]+k-i,d[2*k-i]);
			if(i+d[i]==d[k]+k){
				l=i+d[i],r=i-d[i];
				while(l>=0&&r<n&&b[l]==b[r]){
					l--,r++;
					d[i]++;
					push(i-d[i]+1,i+d[i]-1);
				}
			}
		}else{
			l=r=i;
			while(l>=0&&r<n&&b[l]==b[r]){
				l--,r++;
				d[i]++;
				push(i-d[i]+1,i+d[i]-1);
			}
		}

		if(d[i]>1){
			add(i-d[i]+2,i+d[i]-2);
		}
	}
/*
	for(int i=0;i<n;i++){
		printf("%c",b[i]);
	}
	puts("");

	for(int i=0;i<n;i++){
		printf("%d ",d[i]);
	}
	puts("");*/
}

bool chk[300010];
ll ans=0;

ll dfs(int v){
	chk[v]=1;
	ll z=cnt[v];
	for(int i=0;i<path[v].size();i++){
		int u=path[v][i];
		if(chk[u])continue;
		z+=dfs(u);
	}

	// printf("%d (%lld,%lld) : %lld \n",v,len[v],cnt[v],z);

	ans=max(ans,z*len[v]);
	return z;
}

int main(){

	scanf("%s",a);

	N=strlen(a);
	path.assign(N+1,vec());

	init();
	manacher();
	dfs(0);

	printf("%lld\n",ans);
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27