*Problema 2 (Selectia lotului international, 2004)*

Se considera un sir c ~1~ c ~2~ ...c ~n~ format din n <= 30.000 caractere din multimea {A, B}. Concatenam sirul cu el insusi si obtinem un sir de lungime 2n. Pentru un indice k (1<=k<=2n) consideram subsecventele de lungime cel mult n, care se termina pe pozitia k, iar dintre acestea fie s(k) subsecventa cea mai mica in ordine lexicografica. Determinati indicele k pentru care s(k) are lungimea cea mai mare.
 
*Problema 3*
 
Se dau doua poligoane in plan fiecare avand n<=1000000 varfuri. Poligoanele sunt date prin coordonatele varfurilor lor in ordine trigonometrica. Sa se verifice daca cele doua poligoane sunt asemenea.
 
 

Se considera un sir c ~1~ c ~2~ ...c ~n~ format din n <= 30.000 caractere din multimea {A, B}. Concatenam sirul cu el insusi si obtinem un sir de lungime 2n. Pentru un indice k (1<=k<=2n) consideram subsecventele de lungime cel mult n, care se termina pe pozitia k, iar dintre acestea fie s(k) subsecventa cea mai mica in ordine lexicografica. Determinati indicele k pentru care s(k) are lungimea cea mai mare.