Advertisement
aircampro

vector print and kasai function

Jun 16th, 2021
132
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.82 KB | None | 0 0
  1. //
  2. // Example of showing how to pass a vector to a function (kasai) and print it by various methods
  3. // g++-7 -std=c++17 kasai.cpp -o kasai
  4. //
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>
  8. // select the options to print a vector (default overloading the << operator to recognise the ostream object)
  9. // #define WITH_FUNCTION
  10. // #define OPTION_1
  11. // #define OPTION_2
  12. #define OPTION_3
  13. #if defined(OPTION_3) && defined(WITH_FUNCTION)
  14. #include <algorithm>
  15. #include <iterator>
  16. #endif
  17. using namespace std;
  18.  
  19. vector<int> kasai(string s, vector<int> &sa)
  20. {
  21.     int n=s.size(),k=0;
  22.     vector<int> lcp(n,0);
  23.     vector<int> rank(n,0);
  24.  
  25.     for(int i=0; i<n; i++) rank[sa[i]]=i;
  26.  
  27.     for(int i=0; i<n; i++, k?k--:0)
  28.     {
  29.         if(rank[i]==n-1) {k=0; continue;}
  30.         int j=sa[rank[i]+1];
  31.         while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
  32.         lcp[rank[i]]=k;
  33.     }
  34.     return lcp;
  35. }
  36.  
  37.  
  38. #if defined(WITH_FUNCTION)
  39. void printVector(std::vector<int> const &input)
  40. {
  41. #if defined(OPTION_1)
  42.     for (int i = 0; i < input.size(); i++) {
  43.         std::cout << input.at(i) << ' ';
  44.     }
  45. #elif defined(OPTION_2)
  46.     for (auto const &i: input) {
  47.         std::cout << i << " ";
  48.     }
  49. #elif defined(OPTION_3)
  50.     std::copy(input.begin(),
  51.               input.end(),
  52.               std::ostream_iterator<int>(std::cout, " "));
  53. #endif
  54. }
  55. #else
  56. std::ostream &operator<<(std::ostream &os, const std::vector<int> &input)
  57. {
  58.     for (auto const &i: input) {
  59.         os << i << " ";
  60.     }
  61.     return os;
  62. }
  63. #endif
  64.  
  65. main()
  66. {
  67.     std::string myInput;
  68.    
  69.     cout << "enter the string : " << endl;
  70.     getline(cin,myInput);
  71.     vector<int> vec(myInput.size(),0);
  72.     auto lcp = kasai(myInput, vec);  
  73. #if defined(WITH_FUNCTION)
  74.     printVector(lcp);
  75. #else
  76.     cout << " the vector now prints normally " << lcp << endl;
  77. #endif
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement