Solution:

We need to find the longest palindrome suffix of S.

- compute the Z function for reverse(S)$S
- find the smallest i<n such that i+Z[i] = n
- append reverse(S[1,…,i-1]) to the end of S.

Advertisements

Leave a reply

Solution:

We need to find the longest palindrome suffix of S.

- compute the Z function for reverse(S)$S
- find the smallest i<n such that i+Z[i] = n
- append reverse(S[1,…,i-1]) to the end of S.

Advertisements

Solution:

- compute KMP function f for the input string
- for each i<n, if and print with

The hardest thing here is to prove that this procedure is correct.

Solution:

- compute partial sums array S of A (original array), i.e. S[i]=S[i-1]+A[i-1]. ()
- compute B[i]=min{ S[j] : j<i} for each i<n. ()
- compute C[i]=min{ S[j] : j>=i} for each i<n. ()
- execute the loop below. ()

int res = 0; for(int i=0; i<n; i++) if(C[i]-S[i] <= 0 && B[i]+(S[n]-S[i]) <= 0) res++; return res;

Advertisements