Rezumat problemă

Distanta de editare

#3655

Se dau două șiruri de caractere s și t. Asupra șirului s se pot aplica în mod repetat operațiile:

• șterge un caracter
• inserează un caracter
• modifică un caracter

Pornind de la șirul s se cere să se obțină șirul t aplicând de un număr minim de ori operațiile date.

Folclorul informatic

Consola Pracsiu Dan (dnprx) Dan Pracsiu ușoară

Clasa 11 Programare dinamică Probleme diverse de programare dinamică Distanta Levenshtein

Rezolvă

Detalii

Problema	Distanta de editare	Operații I/O	tastatură/ecran
Limita timp	0.1 secunde	Limita memorie	Total: 64 MB / Stivă 8 MB
Id soluție	#58238003	Utilizator	6B Voiculescu Albert (AlbertTheDood)
Fișier	distanta_de_editare.cpp	Dimensiune	814 B
Data încărcării	21 Mai 2025, 18:29	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

distanta_de_editare.cpp:5:1: error: stray '\342' in program
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

 ^
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\234' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\235' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\231' in program
distanta_de_editare.cpp:5:1: error: stray '\' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\231' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\231' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\230' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\231' in program
distanta_de_editare.cpp:5:1: error: stray '\' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\231' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\234' in program
distanta_de_editare.cpp:5:1: error: stray '\342' in program
distanta_de_editare.cpp:5:1: error: stray '\200' in program
distanta_de_editare.cpp:5:1: error: stray '\234' in program
distanta_de_editare.cpp: In function 'int main()':
distanta_de_editare.cpp:5:104: error: 'dist00' was not declared in this scope
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                        ^
distanta_de_editare.cpp:5:155: error: expected ';' before numeric constant
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                           ^
distanta_de_editare.cpp:5:154: warning: statement has no effect [-Wunused-value]
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                          ^
distanta_de_editare.cpp:5:162: error: 'dist0' was not declared in this scope
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                  ^
distanta_de_editare.cpp:5:233: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                         ^
distanta_de_editare.cpp:5:270: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                              ^
distanta_de_editare.cpp:5:513: error: 'matricea' was not declared in this scope
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 ^
distanta_de_editare.cpp:5:522: error: expected ';' before 'distantelor'
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          ^
distanta_de_editare.cpp:5:575: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                               ^
distanta_de_editare.cpp:5:612: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ^
distanta_de_editare.cpp:5:645: error: expected primary-expression before ';' token
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                     ^
distanta_de_editare.cpp:5:657: error: 'n' was not declared in this scope
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                 ^
distanta_de_editare.cpp:5:676: error: 'distanta' was not declared in this scope
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                    ^
distanta_de_editare.cpp:5:685: error: expected ';' before 'minima'
 int main() { for(int i = 0; i <= 100; i++) { for(int j = 0; j <= 100; j++) { dist[i][j] = INT_MAX; } } dist00 = 0; for(int i = 1; i <= 100; i++) { dist[i]0 = i; dist0[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;

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             ^

Cum funcționează evaluarea?