Vizualizare sursă pentru „3889 - Cnt Subsir Max”

== Cerinţa ==
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 ieșire ==
Să se afișeze suma cerută, modulo 109+7.
== Restricţii şi precizări ==
* 1≤N≤106
== Subtask ==
* N≤15
== Subtask ==
* N≤200
== Subtask ==
* N≤2000
== Subtask ==
* N≤5⋅104
== Subtask ==
* Fară restricții suplimentare.
== Exemplul 1 ==
; Intrare

  cab
; Ieșire

 8
== Explicație ==
Pentru primul exemplu, observăm că m(c) = 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. 
<br>

== Exemplu 2 ==
; Intrare

  felicia
; Ieșire

  59



== Rezolvare ==
<syntaxhighlight lang="python" line>
MOD = 10**9 + 7

def max_lexicographic(s):
    max_substring = s[0]
    for i in range(1, len(s)):
        if s[i] >= max_substring[0]:
            max_substring = s[i] + max_substring
        else:
            max_substring += s[i]
    return max_substring

def sum_of_max_substrings(s):
    total_sum = 0
    for i in range(len(s)):
        max_substring = max_lexicographic(s[i:])
        total_sum += len(max_substring)
        total_sum %= MOD
    return total_sum

def main():
    s = input().strip()
    result = sum_of_max_substrings(s)
    print(result)

if __name__ == "__main__":
    main()

</syntaxhighlight>