| Fişierul intrare/ieşire: | cntsubsirmax.in, cntsubsirmax.out | Sursă | InfoPro, Runda 2, Grupa A |
| Autor | Tamio-Vesa Nakajima | Adăugată de |  Tamio Vesa Nakajima •tamionv |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 256000 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Cntsubsirmax
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.
Date de intrare
Pe singura linie citită de la tastatură se va găsi şirul s.
Date de intrare
Să se afişeze suma cerută, modulo 1.000.000.007.
Restricţii
- 1 ≤ |s| ≤ 1.000.000
- Pentru 20 de puncte, |s| ≤ 15
- Pentru alte 10 de puncte, |s| ≤ 200
- Pentru alte 20 de puncte, |s| ≤ 2.000
- Pentru alte 20 de puncte, |s| ≤ 10.000
Exemple
| cntsubsirmax.in | cntsubsirmax.out |
|---|---|
| cab | 8 |
| felicia | 59 |
Explicaţie
Pentru primul exemplu, observăm că m© = c, m(a) = a, m(b) = b, m(ca) = ca, m(ab) = b, m(cab) = cb. Astfel, răspunsul este 1 + 1 + 1 + 2 + 1 + 2 = 8.
