Category Archives: Problems

Extend to Palindrome

Problem Statement

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.

Period

Problem Statement

Solution:

compute KMP function f for the input string
for each i<n, if $i \mod i-f(i) = 0$ and $f(i)\neq 0$ print $i$ with $k=i/(i-f(i))$

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

Nonnegative Partial Sums

Problem Statement

Solution:

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

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