fork download
copy 
  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.   for(std::istream_iterator<std::string> it(iss1), end; ; ) {
  58.     words1.push_back(*it);
  59.     if(++it == end)
  60.       break;
  61.     words1.push_back(" ");
  62.   }
  63.   for(std::istream_iterator<std::string> it(iss2), end; ; ) {
  64.     words2.push_back(*it);
  65.     if(++it == end)
  66.       break;
  67.     words2.push_back(" ");
  68.   }
  69.   return seq_distance(words1, words2, &word_distance);
  70. }
  71.  
  72. int main(int, char**)
  73. {
  74.   std::cout <<
  75.     word_distance("Hello World",
  76.                   "Hel loWorld") << std::endl;
  77.   std::cout <<
  78.     sentence_distance("Hello World",
  79.                       "Hel loWorld") << std::endl;
  80.   std::cout <<
  81.     word_distance("Al Chertoff Et",
  82.                   "Al Church Department of finance Et") << std::endl;
  83.   std::cout <<
  84.     sentence_distance("Al Chertoff Et",
  85.                       "Al Church Department of finance Et") << std::endl;
  86.   std::cout <<
  87.     word_distance("Al Chertoff Deport Et",
  88.                   "Al Church Department of finance Et") << std::endl;
  89.   std::cout <<
  90.     sentence_distance("Al Chertoff Deport Et",
  91.                       "Al Church Department of finance Et") << std::endl;
  92.   return 0;
  93. }
Success #stdin #stdout 0s 3040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2
4
20
26
21
21
https://ideone.com/RzpNic
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!