fork(2) download
  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <sstream>
  5. #include <iomanip>
  6. using namespace std;
  7. int lcs_len(const vector<string> &vx, const vector<string> &vy)
  8. {
  9. int x_z = vx.size();
  10. int y_z = vy.size();
  11. int c[1001][1001] = {0};
  12.  
  13. /* fill first column of all rows with zero's */
  14. for(int i = 0; i <= x_z; ++i)
  15. c[i][0] = 0;
  16.  
  17. /* fill first row of all column with zero's */
  18. for(int j = 0; j <= y_z; ++j)
  19. c[0][j] = 0;
  20.  
  21. for(int i = 0; i < x_z; ++i)
  22. {
  23. for(int j = 0; j < y_z; ++j)
  24. {
  25. if( vx[i] == vy[j])
  26. c[i+1][j+1] = c[i][j]+1;
  27. else if( c[i][j+1] >= c[i+1][j])
  28. c[i+1][j+1] = c[i][j+1];
  29. else
  30. c[i+1][j+1] = c[i+1][j];
  31. }
  32. }
  33. return c[x_z][y_z];
  34. }
  35.  
  36. int main()
  37. {
  38. int k = 0;
  39. stringstream ss;
  40. string x, y;
  41. while(getline(cin, x))
  42. {
  43. ss.clear();
  44. string word;
  45. vector<string> vx;
  46. vector<string> vy;
  47.  
  48. int xsz = x.size();
  49. for(int i = 0; i < xsz; ++i)
  50. {
  51. if(isalnum(x[i]))
  52. continue;
  53. else
  54. x[i] = ' ';
  55. }
  56. ss << x;
  57. while(!ss.eof())
  58. {
  59. ss >> word;
  60. if(!word.empty())
  61. vx.push_back(word);
  62. }
  63. getline(cin, y);
  64. int ysz = y.size();
  65. for(int i = 0; i < ysz; ++i)
  66. {
  67. if(isalnum(y[i]))
  68. continue;
  69. else
  70. y[i] = ' ';
  71. }
  72. ss.clear();
  73. word.clear();
  74. ss << y;
  75. while(!ss.eof())
  76. {
  77. ss >> word;
  78. if(!word.empty())
  79. vy.push_back(word);
  80. }
  81. if( xsz == 0 || ysz == 0)
  82. printf("%2d. Blank!\n",++k);
  83. else
  84. printf("%2d. Length of longest match: %d\n",++k, lcs_len(vx, vy));
  85. }
  86. return 0;
  87. }
  88.  
Success #stdin #stdout 0.02s 7272KB
stdin
This is a test.
Test
Hello!

The document provides late-breaking information
late breaking.
hello world this is me
,.,me hello this
.,;''l'
34dsf
sdf

sdf me and what the hel.,/ is sd
sdfg asde what the asdasd is sd
The document provides late-breaking information
The breaking.
.,
,.
The34 4 document provides late-breaking information
The34 4
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
This is a test.
test
Hello!

The document provides late-breaking information
late breaking.
a b c
a c
abcd

This is a test.
This is not a Test.
12 12
12 12
12 12
12 12
this is a test
this is is a a test
76.67 67
67 67 76



asd




a s d c f
a d c
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
as de vfdv adas 1212 dfsf wegg 21341wd fwrf3 3ref qwe2
a s d
r t g
.;.;[
.;.;[

hello
a!aa!aaa!
aa
The document provides late-breaking information
late breaking.
aaa a a a a
a
stdout
 1. Length of longest match: 0
 2. Blank!
 3. Length of longest match: 2
 4. Length of longest match: 2
 5. Length of longest match: 0
 6. Blank!
 7. Length of longest match: 4
 8. Length of longest match: 2
 9. Length of longest match: 0
10. Length of longest match: 2
11. Length of longest match: 1
12. Blank!
13. Length of longest match: 2
14. Length of longest match: 1
15. Blank!
16. Length of longest match: 2
17. Length of longest match: 1
18. Blank!
19. Length of longest match: 2
20. Length of longest match: 1
21. Blank!
22. Length of longest match: 2
23. Length of longest match: 2
24. Blank!
25. Length of longest match: 3
26. Length of longest match: 2
27. Length of longest match: 2
28. Length of longest match: 4
29. Length of longest match: 2
30. Blank!
31. Blank!
32. Blank!
33. Blank!
34. Length of longest match: 3
35. Length of longest match: 11
36. Length of longest match: 0
37. Length of longest match: 0
38. Blank!
39. Length of longest match: 1
40. Length of longest match: 2
41. Length of longest match: 1