SHARE
TWEET

Untitled

a guest May 22nd, 2019 62 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include "pch.h"
  2. #include <iostream>
  3. #include <thread>
  4. #include <string>
  5. #include <vector>
  6.  
  7. std::vector<size_t> prefix_function(const std::string& haystack);
  8. std::vector<size_t> knuth_morris_pratt(const std::string& haystack, const std::string& needle, char salt);
  9.  
  10. class KnuthMorrisPrattCompressed
  11. {
  12. public:
  13.     static std::vector<size_t> find(const std::string& haystack, const std::string& needle);
  14. };
  15.  
  16.  
  17. #define FUTILITY
  18.  
  19. std::vector<size_t> prefix_function(const std::string& haystack) {
  20. #ifdef FUTILITY
  21.     std::cout << "calculation of prefix-function..." << std::endl;
  22.     std::cout << "prefix-function value for first character: " << haystack.front() << " equal to: 0" << std::endl << std::endl;
  23. #endif
  24.     std::vector<size_t> result(haystack.length());
  25.     for (size_t i = 1; i < haystack.length(); ++i)
  26.     {
  27. #ifdef FUTILITY
  28.         std::cout << "current character: " << haystack[i] << " (index i: " << i << ")" << std::endl;
  29. #endif
  30.         // by default, result is filled with zeros
  31.         size_t j = result[i - 1];
  32. #ifdef FUTILITY
  33.         std::cout << "last known prefix-function value j: " << j << std::endl;
  34. #endif
  35.         // осуществляем возврат по известным значениям префикс функции
  36.         while (j > 0 && haystack[i] != haystack[j])
  37.         {
  38.             j = result[j - 1];
  39. #ifdef FUTILITY
  40.             std::cout << "s[i] not equal to s[j]: decreasing j: " << j << std::endl;
  41. #endif
  42.         }
  43.         // увеличиваем значение профекс функции на единицу
  44.         if (haystack[i] == haystack[j])
  45.         {
  46.             ++j;
  47. #ifdef FUTILITY
  48.             std::cout << "character are equal: incrementing j: " << j << std::endl;
  49. #endif
  50.         }
  51. #ifdef FUTILITY
  52.         std::cout << "prefix-function value found: " << j << std::endl << std::endl;
  53. #endif
  54.         result[i] = j;
  55.     }
  56. #ifdef FUTILITY
  57.     std::cout << "calculation of prefix-function ends" << std::endl;
  58. #endif
  59.     // using move semantics
  60.     return std::move(result);
  61. }
  62.  
  63. std::vector<size_t> knuth_morris_pratt(const std::string& haystack, const std::string& needle, char salt) {
  64.     std::vector<size_t> result;
  65.     std::vector<size_t> prefix = prefix_function(needle + salt + haystack);
  66. #ifdef FUTILITY
  67.     std::cout << "prefix-function prefix-function values: " << std::endl;
  68.     for (size_t i = 0; i < needle.length(); ++i)
  69.         std::cout << needle[i] << " ";
  70.     std::cout << salt << " ";
  71.     for (size_t i = 0; i < haystack.length(); ++i)
  72.         std::cout << haystack[i] << " ";
  73.     std::cout << std::endl;
  74.     for (size_t i = 0; i < prefix.size(); ++i)
  75.         std::cout << prefix[i] << " ";
  76.     std::cout << std::endl;
  77. #endif
  78.     for (size_t i = 0; i < haystack.length(); ++i)
  79.     {
  80.         // найдено вхождение
  81.         if (prefix[needle.length() + i + 1] == needle.length())
  82.         {
  83.             // добавляем индекс в выходные данные с учётом сдвига
  84.             result.push_back(i + 1 - needle.length());
  85.         }
  86.     }
  87.     // using move semantics
  88.     return std::move(result);
  89. }
  90.  
  91. std::vector<size_t> KnuthMorrisPrattCompressed::find(const std::string& haystack, const std::string& needle)
  92. {
  93.     std::vector<size_t> entries;
  94.  
  95.     size_t p = needle.length();
  96.     size_t t = haystack.length();
  97.  
  98.     if (p > t || p == 0)
  99.         return (std::move(entries));
  100.  
  101.     std::vector<size_t> prefix = prefix_function(needle);
  102.  
  103. #ifdef FUTILITY
  104.     std::cout << "prefix-function prefix-function values: " << std::endl;
  105.     for (size_t i = 0; i < needle.length(); ++i)
  106.         std::cout << needle[i] << " ";
  107.     std::cout << std::endl;
  108.     for (size_t i = 0; i < prefix.size(); ++i)
  109.         std::cout << prefix[i] << " ";
  110.     std::cout << std::endl;
  111. #endif
  112.  
  113.     for (size_t i = 0, k = 0; i < t; ++i)
  114.     {
  115.         while (true)
  116.         {
  117.             if (haystack[i] == needle[k])
  118.             {
  119.                 ++k;
  120.                 if (k == p)
  121.                     entries.push_back(i + 1 - p);
  122.                 break;
  123.             }
  124.             if (k == 0)
  125.                 break;
  126.             k = prefix[p - 1];
  127.         }
  128.     }
  129.  
  130.     return (std::move(entries));
  131. }
  132.  
  133. int main() {
  134.     std::string needle;
  135.     std::cin >> needle;
  136.  
  137.     std::string haystack;
  138.     std::cin >> haystack;
  139.  
  140.     std::vector<size_t> entries = KnuthMorrisPrattCompressed::find(haystack, needle);
  141.  
  142.     // no entries found
  143.     if (entries.empty())
  144.     {
  145.         std::cout << -1 << std::endl << std::endl;
  146.         return EXIT_SUCCESS;
  147.     }
  148.  
  149.     for (size_t i = 0; i < entries.size() - 1; ++i)
  150.         std::cout << entries[i] << ',';
  151.     std::cout << entries.back() << std::endl << std::endl;
  152.  
  153.     return EXIT_SUCCESS;
  154. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top