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.

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>