Problema este foarte grea. A fost data prima oara la Olimpiada poloneza din 2004. Poti gasi o rezolvare cu suffix array
in articolul de pe site (problema Template). Eu nu mai tin minte cum se face in O(N), poate te ajuta cei care au facut-o in concurs la campion.