Advertisement
Guest User

muie badii

a guest
Nov 21st, 2019
104
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.90 KB | None | 0 0
  1. #include <cstring>
  2. #include <fstream>
  3.  
  4. using namespace std;
  5.  
  6. char s1[1001], s2[1001];
  7.  
  8. int n, m, p[1001][1001];
  9.  
  10. ifstream fin("subsircomunmaximal.in");
  11. ofstream fout("subsircomunmaximal.out");
  12.  
  13. void citire()
  14. {
  15. fin>>s1+1>>s2+1;
  16. n=strlen(s1+1);
  17. m=strlen(s2+1);
  18. }
  19.  
  20. void drum(int i, int j)
  21. {
  22. if(i != 0 && j !=0)
  23. {
  24. if(p[i][j]==p[i-1][j-1]+1 && s1[i]==s2[j])
  25. {
  26. drum(i-1,j-1);
  27. fout<<s1[i];
  28.  
  29. }
  30. else
  31. if(p[i-1][j]>=p[i][j-1])
  32. drum(i-1,j);
  33. else
  34. drum(i,j-1);
  35. }
  36. }
  37.  
  38. void scm()
  39. {
  40. for(int i=1; i<=n; i++)
  41. for(int j=1; j<=m; j++)
  42. if(s1[i]==s2[j])
  43. p[i][j]=p[i-1][j-1]+1;
  44. else
  45. p[i][j]=max(p[i-1][j], p[i][j-1]);
  46. }
  47.  
  48. int main()
  49. {
  50. citire();
  51. scm();
  52. drum(n,m);
  53. return 0;
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement