Guest User

Untitled

a guest
Feb 18th, 2018
79
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.86 KB | None | 0 0
  1. #include <iostream>
  2.  
  3.  
  4. using namespace std;
  5.  
  6. int main() {
  7. int a=0,b=0,c=0;
  8. cin>>a;
  9. int taba[a];
  10. for(int i=0;i<a;i++){
  11. cin>>c;
  12. taba[i]=c;
  13. }
  14. cin>>b;
  15. int tabb[b];
  16. for(int i=0;i<b;i++){
  17. cin>>c;
  18. tabb[i]=c;
  19. }
  20.  
  21. int tab[a+1][b+1];
  22. for(int i=0;i<=a;i++){
  23. tab[i][0]=i;
  24. }
  25. for(int i=0;i<=b;i++){
  26. tab[0][i]=i;
  27. }
  28. for(int i=1;i<=a;i++){
  29. for(int j=1;j<=b;j++){
  30. if(taba[i]==tabb[j])
  31. tab[i][j]=min( tab[i-1][j-1],min(tab[i-1][j]+1,tab[i][j-1]+1));
  32. else
  33. tab[i][j]=min( tab[i-1][j-1],min(tab[i-1][j],tab[i][j-1]))+1;
  34. }
  35. }
  36. cout<<tab[a][b];
  37. return 0;
  38. }
Add Comment
Please, Sign In to add comment