Lista de probleme 1

Felicia este interesată de subșirul maxim lexicografic al unui șir de caractere. Rețineți că un șir a este considerat mai mic în ordine lexicografică decât un șir b dacă a este prefix al lui b, sau dacă există o poziție i pentru care avem a[1] = b[1], ..., a[i − 1] = b[i − 1], și a[i] < b[i]. Astfel, subșirul maxim lexicografic al unui șir de caractere este cel mai mare subșir, în ordinea lexicografică, al unui șir de caractere (de exemplu zzxx pentru azbxazbxaax). Pentru un șir s de caractere vom nota cu m(s) subșirul maxim lexicografic al lui s, și cu v(s) = |m(s)| lungimea acestui subșir. Felicia vă dă un șir s format din caractere mici ale alfabetului englez. Considerați toate subsecvențele continue s' ale lui s. Felicia vrea să calculați suma valorilor v(s') pentru toate subsecvențele posibile s' amintite anterior