Articole

Distanța Levenshtein

În informatică, distanța Levenshtein dintre două cuvinte s și t se definește ca fiind numărul minim necesar de operații ce se pot efectua, pentru a schimba un cuvânt în celălalt. Operațiile se pot efectua la nivel de caracter și pot fi de tipul: inserare, ștergere sau înlocuire. Este numită și distanță de editare, problema fiind definită de matematicianul rus Vladimir Levenshtein în 1965.

Exemplu: pentru s=”marina” (n=6) și t=”animat” (m=6) numărul minim de operații necesar pentru a transforma pe s în t este 4:

marina ⇒ arina ⇒ anina ⇒ anima ⇒ animat

Observăm că numărul de operații necasar pentru a transforma șirul s în șirul t este mai mic sau egal cu maximul dintre n și m.
Pornind de la șirul s numărăm operațiile care se fac asupra șirului inițial pornind de la stânga spre dreapta pentru a obține șirul t.
Considerăm o matrice dist cu n+1 linii și m+1 coloane în care dist[i][j] reprezintă numărul minim de operații necesar pentru a transforma primele i caractere din șirul s în primele j caractere din șirul t. În particular dist⁰[j] reprezintă numărul minim de transformări necesare pentru a transforma șirul vid în primele j caractere din șirul t, iar dist[i]⁰ reprezintă numărul minim de transformări necesare pentru a transforma primele i caractere din șirul s în șirul vid.

dist[i][j]=j dacă i==0
dist[i][j]=i dacă j==0
dist[i][j]=dist[i-1][j-1] dacă i!=0 și j!=0 și s[i]==t[j]
dist[i][j]=1+min⁡{dist[i-1][j-1],dist[i][j-1],dist[i-1][j]),altfel

La fiecare pas se compară caracterul s[i] cu t[j].
Dacă s[i]==t[j] atunci nu se face nici o modificare și dist[i][j]=dist[i-1][j-1]
Dacă s[i]!=t[j] atunci putem să avem următoarele situațiile: Adăugarea unui caracter în t[j] caz în care dist[i][j]=1+dist[i][j-1] Ștergerea caracterului s[i] caz în care dist[i][j]=1+dist[i-1][j] Modificarea lui s[i] în t[j] caz în care dist[i][j]=1+dist[i-1][j-1]

Exemplu: pentru s=”marina” (n=6) și t=”animat” (m=6) Pentru a transforma șirul vid în cuvântul ”animat”) formăm linia 0 a matricii cu valorile:
0 1 2 3 4 5 6
(explicație: 0 operații pentru a transforma șirul vid în șirul vid, 1 operație pentru a transforma șirul vid în șirul ”a”, 2 operații pentru a transforma șirul vid în șirul ”an”… 6 operații pentru a transforma șirul vid în șirul”animat”)
Pentru a transforma șirul ”m” în șirul ”animat” formăm linia 1 a matricii cu valorile:
1 1 2 3 3 4 5
(explicație: 1 operație pentru a transforma șirul ”m” în șirul vid, 1 operație pentru a transforma șirul ”m” în șirul ”a”, 2 operații pentru a transforma șirul ”m” în șirul ”an”… 3 operații pentru a transforma șirul”m” în șirul ”ani”, tot 3 operații pentru a transforma șirul ”m” în șirul”anim”(de exemplu 3 inserări”)…6 operații pentru a transforma șirul ”m” în șirul”animat”)
……
Pentru a transforma șirul ”marina” în șirul ”animat” formăm ultima linie din matrice cu valorile:
6 5 4 4 4 4 3 4
(explicație: 6 operații pentru a transforma șirul ”marina” în șirul vid, 5 operații pentru a transforma șirul ”marina” în șirul ”a”, 4 operații pentru a transforma șirul ”marina” în șirul ”an”(ștergem literele m,r,i și a)… 4 operații pentru a transforma șirul”marina” în șirul ”animat)
Matricea va fi:
0 1 2 3 4 5 6
1 1 2 3 3 4 5
2 1 2 3 4 3 4
3 2 2 3 4 4 4
4 3 3 2 3 4 5
5 4 3 3 3 4 5
6 5 4 4 4 3 4

Numărul minim de operații pentru acest exemplu va fi dist [6] [6] adică 4

#include <bits/stdc++.h>
using namespace std;
int dist [105] [105];

int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist⁰⁰ = 0; for(int i = 1; i <= 100; i++) { dist[i]⁰ = i; dist⁰[i] = i; } string s, t; cin >> s >> t; for(int i = 1; i <= s.size(); i++) { for(int j = 1; j <= t.size(); j++) { if(s[i-1] == t[j-1]) { dist[i][j] = min(dist[i][j], dist[i-1][j-1]); } else { dist[i][j] = min(dist[i][j], 1+dist[i-1][j-1]); } dist[i][j] = min(dist[i][j], 1+dist[i-1][j]); dist[i][j] = min(dist[i][j], 1+dist[i][j-1]); } } cout<<“matricea distantelor”<<’\n’; for(int i = 0; i <= s.size(); i++) { for(int j = 0; j <= t.size(); j++) cout<<dist[i][j]<<’ ‘; cout<<’\n’; } cout << “distanta minima este : “<<dist[s.size()][t.size()]; return 0;
}

Hai să discutăm despre două chestii esențiale în C++: array-urile și std::vector. Ambele au locul lor în codul tău, dar fiecare are avantaje și dezavantaje. Deci, ce să alegi?

Array-uri C
Array-urile în C sunt super rapide. De ce? Pentru că sunt foarte simple. Când declari un array, el are o dimensiune fixă și stă într-un loc în memorie. Asta înseamnă că accesarea elementelor din array e aproape instantanee.

Avantaje:
- Rapiditate maximă.
- Simplu de folosit pentru dimensiuni fixe.

Dezavantaje:
- Dimensiune fixă, nu poți adăuga elemente după ce ai declarat array-ul.
- Nu e foarte flexibil, trebuie să știi din start cât de mare trebuie să fie.

std::vector
Aici intervine std::vector. E ca un array pe steroizi – îți permite să adaugi elemente la final cu push_back. Pare grozav, nu? Dar are un cost.

Când dai push_back și vectorul nu mai are spațiu, el își dublează capacitatea și copiază toate elementele într-o altă zonă de memorie. Asta poate să fie destul de lent dacă faci asta des.

Avantaje:
- Flexibilitate, poți adăuga și șterge elemente.
- Funcții utile, cum ar fi sortarea sau căutarea.

Dezavantaje:
- Poate deveni lent la push_back frecvent din cauza realocărilor.
- Consumă mai multă memorie decât un array simplu.

Deci, ce alegi?
Dacă știi din start câte elemente vei avea și performanța e crucială, un array C e calea. Simplu și rapid.

Dacă ai nevoie de flexibilitate și nu știi dimensiunea finală, std::vector e prietenul tău. Da, poate fi mai lent dacă faci multe push_back, dar dacă îți faci treaba corect și te asiguri că vectorul e suficient de mare de la început (folosind reserve), nu vei avea probleme majore de performanță.

Concluzie
Folosește array-uri C pentru rapiditate și eficiență maximă atunci când știi dimensiunea fixă. Folosește std::vector pentru flexibilitate și lejeritate, dar ai grijă cum gestionezi capacitatea ca să eviți realocările frecvente.

Autor: Gabriel de la meditatii-informatica | sustinut de infoarena

Puteti fi si prof si elev daca la profil bifati ambele optiuni:sunt elev,sunt profesor
100% true👍

daca la profil bifati si profesor,si elev, o sa puteti fi amandoua si ceti putea crea clase ca elev.
100% true!👍

cashaajj

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin(“perle.in”);
ofstream fout (“perle.out”);
int n;
vector <int> v;

bool Perla( char c)
{ stack<char> stk; int p = 1; char l; stk.push( c );

}

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream fin(“perle.in”);
ofstream fout (“perle.out”);
int n;
vector <int> v;

bool Perla( char c)
{ stack<char> stk; int p = 1; char l; stk.push( c );

}

#include <bits/stdc++.h>
using namespace std;

ifstream fin(“donjon.in”);
ofstream fout(“donjon.out”);

#define cin fin
#define cout fout

int main()
{ int t; cin >> t; while (t—) { int64_t n, k; cin >> n >> k; int64_t ans = (2 * n – k * k + k) / (2 * k); if ((2 * n – k * k + k) % (2 * k) == 0 && ans > 0) { int xr = 0; int x; for (x = ans; x < ans + k && x % 4; ++x) xr ^= x; for (int y = ans + k – 1; y >= x && (y + 1) % 4; —y) xr ^= y; cout << (xr ? ‘G’:‘C’) << ‘ ‘ << ans << ‘\n’; } else cout << “C\n”; }
}

#include <bits/stdc++.h>
using namespace std;

ifstream fin (“ghicitoare.in”);
ofstream fout (“ghicitoare.out”);
#define cin fin
#define cout fout

int n, x, T, k;

int xor_n (int n)
{ switch(n % 4){ case 0: return n; break; case 1: return 1; break; case 2: return n + 1; break; case 3: return 0; break; }

}

int main()
{ cin >> T; while(T—){ cin >> n >> k; x = xor_n(n); x ^= k; cout << x << “\n”; } return 0;

}

#include <iostream>
#include <vector>

bool estePrim(int numar) { if (numar < 2) { return false; } for (int i = 2; i * i <= numar; i++) { if (numar % i == 0) { return false; } } return true;
}

int main() { int n; std::cout << “Introduceti numarul de elemente: “; std::cin >> n;