fork(2) download
  1. #include <iterator>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <string>
  5. #include <sstream>
  6. #include <iostream>
  7.  
  8. template<typename T, typename C>
  9. size_t
  10. seq_distance(const T& seq1, const T& seq2, const C& cost,
  11. const typename T::value_type& empty = typename T::value_type()) {
  12. const size_t size1 = seq1.size();
  13. const size_t size2 = seq2.size();
  14.  
  15. std::vector<size_t> curr_col(size2 + 1);
  16. std::vector<size_t> prev_col(size2 + 1);
  17.  
  18. // Prime the previous column for use in the following loop:
  19. prev_col[0] = 0;
  20. for (size_t idx2 = 0; idx2 < size2; ++idx2) {
  21. prev_col[idx2 + 1] = prev_col[idx2] + cost(empty, seq2[idx2]);
  22. }
  23.  
  24. for (size_t idx1 = 0; idx1 < size1; ++idx1) {
  25. curr_col[0] = curr_col[0] + cost(seq1[idx1], empty);
  26.  
  27. for (size_t idx2 = 0; idx2 < size2; ++idx2) {
  28. curr_col[idx2 + 1] = std::min(std::min(
  29. curr_col[idx2] + cost(empty, seq2[idx2]),
  30. prev_col[idx2 + 1] + cost(seq1[idx1], empty)),
  31. prev_col[idx2] + cost(seq1[idx1], seq2[idx2]));
  32. }
  33.  
  34. curr_col.swap(prev_col);
  35. curr_col[0] = prev_col[0];
  36. }
  37.  
  38. return prev_col[size2];
  39. }
  40.  
  41. size_t
  42. letter_distance(char letter1, char letter2) {
  43. return letter1 != letter2 ? 1 : 0;
  44. }
  45.  
  46. size_t
  47. word_distance(const std::string& word1, const std::string& word2) {
  48. return seq_distance(word1, word2, &letter_distance);
  49. }
  50.  
  51. size_t
  52. sentence_distance(const std::string& sentence1, const std::string& sentence2) {
  53. std::vector<std::string> words1;
  54. std::vector<std::string> words2;
  55. std::istringstream iss1(sentence1);
  56. std::istringstream iss2(sentence2);
  57. std::copy(std::istream_iterator<std::string>(iss1),
  58. std::istream_iterator<std::string>(),
  59. std::back_inserter< std::vector<std::string> >(words1));
  60. std::copy(std::istream_iterator<std::string>(iss2),
  61. std::istream_iterator<std::string>(),
  62. std::back_inserter< std::vector<std::string> >(words2));
  63. return seq_distance(words1, words2, &word_distance);
  64. }
  65.  
  66. int main(int, char**)
  67. {
  68. std::cout <<
  69. word_distance("Hello World",
  70. "Hel loWorld") << std::endl;
  71. std::cout <<
  72. sentence_distance("Hello World",
  73. "Hel loWorld") << std::endl;
  74. std::cout <<
  75. word_distance("Al Chertoff Et",
  76. "Al Church Department of finance Et") << std::endl;
  77. std::cout <<
  78. sentence_distance("Al Chertoff Et",
  79. "Al Church Department of finance Et") << std::endl;
  80. std::cout <<
  81. word_distance("Al Chertoff Deport Et",
  82. "Al Church Department of finance Et") << std::endl;
  83. std::cout <<
  84. sentence_distance("Al Chertoff Deport Et",
  85. "Al Church Department of finance Et") << std::endl;
  86. return 0;
  87. }
Success #stdin #stdout 0s 2996KB
stdin
Standard input is empty
stdout
2
4
20
23
21
19