# PBinfo #3719 – SDistante – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

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".

Cerința
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 1.000.000.007. 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 1.000.000.007. |s| reprezintă lungimea șirului s, care este indexat de la 0.

Date de intrare
Fișierul de intrare sdistante.in conține pe prima linie ș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 1.000.000.007.

Restricții și precizări

1 ≤ |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| ≤ 1000 și s conține doar caracterele a și b
Pentru alte 30 puncte, |s| ≤ 5000 ș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
Pentru alte 6 puncte, fără restricții

Exemplul 1:
sdistante.in

abc
sdistante.out

5
Explicație

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

Exemplul 2:
sdistante.in

aab
sdistante.out

3
Explicație

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

Exemplul 3:
sdistante.in

ABa
sdistante.out

5
Explicație

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

Exemplul 4:
sdistante.in

aaaaabbbaaaa
sdistante.out

480
Exemplul 5:
sdistante.in

abcdefghizabcdefghiz
sdistante.out

7095

## Cod sursă C++

```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
  ifstream cin("sdistante.in");
  ofstream cout("sdistante.out");
  string s; cin >> s;
  vector<long long> cnt(256, 0);
  long long ans = 0, tot = 0;
  for (int i = 0; i < (int)s.size(); ++i) {
    ans = (ans + (tot - cnt[s[i]]) * (s.size() - i)) % 1000000007;
    tot += i + 1; cnt[s[i]] += i + 1;
  }
  cout << ans << endl;
  return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3719)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3719/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3719/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)