Can somebody give hints to solve this task?

Conflict graph may help.
Positions of possible substrings are vertices and two positions
conflict if they  can not be  simultaneously.
Answer= max number of independent vertices.
Also let relation a<b means that position is before of  position b and they don't conflict.Then a<b,b<c=> a<c so we have an order. Answer is a height of ordered structure.

Edited by author 08.10.2011 19:07

Just easy DP.

But Dp may be difficult- problem of 35 test.
When poset is used and standard dfs for it's height we have Ac without any problems.