[Manacher] Codechef TACHEMIS

http://www.codechef.com/problems/TACHEMIS

Algorithm:

Áp dụng manacher cho n compressed string

Do nếu các các compressed string ghép lại đk thành 1 PS thì độ dài của PS đó chắc chắn lẻ nên ta ko cần bước thêm các "#" như Manacher nguyên bản

int C = 1, R = 1;
a[0]=MP('#',0);
a[n+1]=MP('@',0);

for (int i = 1; i <=n ; i++) {
int i_mirror = 2*C-i;
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
while (a[i + 1 + P[i]] == a[i - 1 - P[i]]) P[i]++;
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}

Với Compressed String a[i]:

- nếu ko ghép với các CS khác:sẽ có a[i].S*(a[i].S+1)/2 xâu palin được tạo thành

Ví dụ A 3 = AAA => Có 6 PS là A,A,A,AA,AA,AAA

- nếu ghép với các CS khác (khi và chỉ khi P[i]>0)

trước hết ta phải trừ đi lượng xâu đã tính ở bước trên (các xâu chi gồm các kí tự giong nhau)

res-=(a[i].S+1)/2;

Sau đó cộng vào lượng palin mới tạo được khi ghép với các CS khác:
int u=i-P[i];
int v=i+P[i];
res+=(sum[v]-sum[u-1]+1)/2;

Chú ý nếu a[i-1] và a[i+1] có số lượng kí tự khác nhau nhưng cùng 1 loạt kí tự thì ta phải cộng thêm vào kết quả min(a[i-1].S,a[i+1].S)

if (a[u-1].F==a[v+1].F) res+=min(a[u-1].S,a[v+1].S);

(Ví dụ

ccccbbabbc

a[1].F=a[5].F='c'

res+=min(a[1].S,a[5].S))

Fullcode:

void Manacher()
{
SET(P,0);
int C = 1, R = 1;
a[0]=MP('#',0);
a[n+1]=MP('@',0);

for (int i = 1; i <=n ; i++) {
int i_mirror = 2*C-i;
P[i] = (R > i) ? min(R-i, P[i_mirror]) : 0;
while (a[i + 1 + P[i]] == a[i - 1 - P[i]]) P[i]++;
if (i + P[i] > R) {
C = i;
R = i + P[i];
}
}
sum[0]=0;
FOR(i,1,n) sum[i]=sum[i-1]+a[i].S;
ll res=0;
FOR(i,1,n) res=res+(ll)(a[i].S+1)*(ll)(a[i].S)/2;
FOR(i,1,n)
{
if (P[i]>0)
{
res-=(a[i].S+1)/2;
int u=i-P[i];
int v=i+P[i];
res+=(sum[v]-sum[u-1]+1)/2;
if (a[u-1].F==a[v+1].F) res+=min(a[u-1].S,a[v+1].S);
}
else
if (a[i-1].F==a[i+1].F) res+=min(a[i-1].S,a[i+1].S);
}
cout<<res<<endl;
}