fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. std::size_t overlap(const std::string& key, const std::string& word);
  7. std::size_t forwardOverlap(const std::string&, const std::string&);
  8. std::size_t reverseOverlap(const std::string&, const std::string&);
  9.  
  10. struct wordInfo
  11. {
  12.     std::size_t expectedOverlap;
  13.     std::string word;
  14. };
  15.  
  16. void testOverlap(const std::string& key, const std::vector<wordInfo>& words)
  17. {
  18.     for (auto& word : words)
  19.     {
  20.         std::size_t overlapSize = overlap(key, word.word);
  21.         if (overlapSize != word.expectedOverlap)
  22.         {
  23.             std::cout << "overlap failed on key \"" << key;
  24.             std::cout << "\" with word \"" << word.word << "\"\n";
  25.             return;
  26.         }
  27.         //else
  28.         //{
  29.         //    std::cout << "overlap succeeded on key \"" << key;
  30.         //    std::cout << "\" with word \"" << word.word << "\": ";
  31.         //    std::cout << overlapSize << " overlap.\n";
  32.         //}
  33.     }
  34.  
  35.     std::cout << "overlap test successful!\n";
  36. }
  37.  
  38.  
  39. int main()
  40. {
  41.     std::vector<wordInfo> words =
  42.     {
  43.         { 0, "fact" }, 
  44.         { 0, "war" }, 
  45.         { 0, "stare" }, 
  46.         { 2, "cent" }, 
  47.         { 4, "facet" }, 
  48.         { 4, "endface" },
  49.         { 2, "alfalfa" }
  50.     };
  51.  
  52.     testOverlap("face", words);
  53. }
  54.  
  55. std::size_t overlap(const std::string& key, const std::string& word)
  56. {
  57.     return std::max(forwardOverlap(key, word), reverseOverlap(key, word));
  58. }
  59.  
  60. std::size_t forwardOverlap(const std::string& k, const std::string& w)
  61. {
  62.     std::size_t overlapSize = std::min(k.size(), w.size());
  63.  
  64.     while (overlapSize > 0)
  65.     {
  66.         std::string keyFragment = k.substr(k.size() - overlapSize);
  67.         std::string wordFragment = w.substr(0, overlapSize);
  68.  
  69.         if (keyFragment == wordFragment)
  70.             break;
  71.  
  72.         --overlapSize;
  73.     }
  74.  
  75.     return overlapSize;
  76. }
  77.  
  78. std::size_t reverseOverlap(const std::string& k, const std::string& w)
  79. {
  80.     std::size_t overlapSize = std::min(k.size(), w.size()) ;
  81.  
  82.     while (overlapSize > 0)
  83.     {
  84.         std::string keyFragment = k.substr(0, overlapSize);
  85.         std::string wordFragment = w.substr(w.size() - overlapSize);
  86.  
  87.         if (keyFragment == wordFragment)
  88.             break;
  89.  
  90.         --overlapSize;
  91.     }
  92.  
  93.     return overlapSize;
  94. }
  95.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
overlap test successful!
https://ideone.com/r7KHpP
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!