Link: http://codeforces.com/contest/7/problem/D
The main challenge is to determine whether a prefix is a palindrome or not.
This can be solved using the Z algorithm in O(n).
We concatenate the string with its reverse.
The idea is that if a prefix ending at position i is a palindrome, then (z[2*n-i-1]>=(i+1)).
For each such prefix we set dp[i]=1, and then increase it with the dp value of the prefix ending in its middle (differs whether its length is even or odd).
The main challenge is to determine whether a prefix is a palindrome or not.
This can be solved using the Z algorithm in O(n).
We concatenate the string with its reverse.
The idea is that if a prefix ending at position i is a palindrome, then (z[2*n-i-1]>=(i+1)).
For each such prefix we set dp[i]=1, and then increase it with the dp value of the prefix ending in its middle (differs whether its length is even or odd).
No comments:
Post a Comment