Fişierul intrare/ieşire:	sdistante.in, sdistante.out	Sursă	OJSEPI 2021, clasa a 10-a
Autor	Bogdan Pop	Adăugată de	Tamio Vesa Nakajima •tamionv
Timp execuţie pe test	0.15 sec	Limită de memorie	64000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sdistante

Definim distanţa dintre două şiruri de caractere de aceeaşi lungime ca fiind numărul minim de caractere ce trebuie modificate (înlocuite fiecare cu câte un alt caracter) în primul şir pentru a obţine al doilea şir. Vom nota distanţa dintre şirurile a şi b cu dist(a, b).

De exemplu, dist(abc, aaa) = 2 (înlocuim caracterul b cu a, respectiv caracterul c cu a), iar dist(ABC, abc) = 3 (literele mici se consideră diferite de cele mari).

Definim o subsecvenţă a unui şir s de caractere ca fiind un şir format din caractere de pe poziţii consecutive din s. Considerăm două subsecvenţe ca fiind distincte dacă încep sau se termină la poziţii diferite. Vom nota cu s(i, j) subsecvenţa formată din caracterele indexate de la i la j ale şirului s. Şirurile se indexează de la 0. Exemplu: pentru şirul s = abc subsecvenţele sunt s(0, 0) = a, s(1,1) = b, s(2,2) = c, s(0,1) = ab, s(1,2) = bc, s(0,2) = abc, iar pentru şirul s= aa acestea sunt s(0,0) = a, s(1,1) = a, s(0,1) = aa.

Se dă un şir de caractere s, care poate conţine doar litere mici şi mari ale alfabetului englez (de la a la z şi de la A la Z). Pentru toate perechile neordonate de subsecvenţe distincte ale şirului s care au lungimi egale, vrem să calculăm distanţa dintre ele şi să afişăm suma acestora modulo 10⁹ + 7. Formal, se cere suma valorilor dist(s(a, b), s(c, d)), pentru toţi indicii a, b, c, d cu 0 ≤ a, b, c, d < |s|, a < c, a ≤ b, c ≤ d, b-a = d-c, modulo 10⁹ + 7. |s| reprezintă lungimea şirului s, care este indexat de la 0.

Date de intrare

Pe singura linie a fişierului sdistante.in este şirul dat, s.

Date de ieşire

Se va afişa pe singurul rând al fişierului sdistante.out un număr întreg reprezentând suma distanţelor, modulo 10⁹ + 7.

Restricţii şi precizări

• |s| ≤ 4.000.000, unde |s| este lungimea şirului s
• Pentru 11 puncte |s| ≤ 20 şi s conţine doar litere mici.
• Pentru alte 5 puncte |s| ≤ 50 şi s conţine doar caracterele a şi b.
• Pentru alte 15 puncte |s| ≤ 350 şi s conţine doar litere mici.
• Pentru alte 6 puncte |s| ≤ 1.000 şi s conţine doar caracterele a şi b.
• Pentru alte 30 de puncte |s| ≤ 5.000 şi s conţine doar litere mici.
• Pentru alte 5 puncte |s| ≤ 100.000 şi s conţine doar caracterele a şi b.
• Pentru alte 4 puncte |s| ≤ 100.000 şi s conţine doar litere mici.
• Pentru alte 6 puncte |s| ≤ 1.000.000 şi s conţine doar caracterele a şi b.
• Atenţie! Este posibil ca punctajul să difere faţă de cel luat în concurs.

Exemple

Explicaţii

Pentru primul exemplu,

• dist(s(0,0), s(1, 1)) = dist(a, b) = 1
• dist(s(0,0), s(2, 2)) = dist(a, c) = 1
• dist(s(1,1), s(2, 2)) = dist(b, c) = 1
• dist(s(0,1), s(1, 2)) = dist(ab, bc) = 2

Pentru al doilea exemplu,

• dist(s(0,0), s(1, 1)) = dist(a, a) = 0
• dist(s(0,0), s(2, 2)) = dist(a, b) = 1
• dist(s(1,1), s(2, 2)) = dist(a, b) = 1
• dist(s(0,1), s(1, 2)) = dist(aa, ab) = 1

Pentru al treilea exemplu,

• dist(s(0,0), s(1, 1)) = dist(A, B) = 1
• dist(s(0,0), s(2, 2)) = dist(A, a) = 1
• dist(s(1,1), s(2, 2)) = dist(B, a) = 1
• dist(s(0,1), s(1, 2)) = dist(AB, Ba) = 2

Cum se trimit solutii?