Revizia anterioară Revizia următoare
| 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 \textit{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 \textit{dist}(a, b).
De exemplu, \textit{dist}( ``\texttt{abc}", ``\texttt{aaa}") = 2 (înlocuim caracterul `\texttt{b}' cu `\texttt{a}', respectiv caracterul `\texttt{c}' cu `\texttt{a}'), iar \textit{dist}(``\texttt{ABC}", ``\texttt{abc}") = 3 (literele mici se consideră diferite de cele mari).
Definim o \textit{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=``\texttt{abc}" subsecvenţele sunt s(0, 0)= ``\texttt{a}", s(1,1)= ``\texttt{b}”, s(2,2)= ``\texttt{c}”, s(0,1)= ``\texttt{ab}", s(1,2)=``\texttt{bc}", s(0,2)=``\texttt{abc}", iar pentru şirul s= ``\texttt{aa}" acestea sunt s(0,0)=``\texttt{a}", s(1,1)=``\texttt{a}", s(0,1)= ``\texttt{aa}".
Se dă un şir de caractere s, care poate conţine doar litere mici şi mari ale alfabetului englez (de la `\texttt{a}' la `\texttt{z}' şi de la `\texttt{A}' la `\texttt{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 109 + 7. Formal, se cere suma valorilor \textit{dist}( s(a, b), s(c, d) ), pentru toţi indicii a, b, c, d cu 0 \le a, b, c, d < |s|, a < c, a \le b, c \le d, b-a = d-c, \textbf{modulo \mathbf{109 + 7}}. |s| reprezintă lungimea şirului s, care este indexat de la 0.
Date de intrare
Fişierul de intrare sdistante.in ...
Date de ieşire
În fişierul de ieşire sdistante.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| sdistante.in | sdistante.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
