Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // Example of showing how to pass a vector to a function (kasai) and print it by various methods
- // g++-7 -std=c++17 kasai.cpp -o kasai
- //
- #include <iostream>
- #include <string>
- #include <vector>
- // select the options to print a vector (default overloading the << operator to recognise the ostream object)
- // #define WITH_FUNCTION
- // #define OPTION_1
- // #define OPTION_2
- #define OPTION_3
- #if defined(OPTION_3) && defined(WITH_FUNCTION)
- #include <algorithm>
- #include <iterator>
- #endif
- using namespace std;
- vector<int> kasai(string s, vector<int> &sa)
- {
- int n=s.size(),k=0;
- vector<int> lcp(n,0);
- vector<int> rank(n,0);
- for(int i=0; i<n; i++) rank[sa[i]]=i;
- for(int i=0; i<n; i++, k?k--:0)
- {
- if(rank[i]==n-1) {k=0; continue;}
- int j=sa[rank[i]+1];
- while(i+k<n && j+k<n && s[i+k]==s[j+k]) k++;
- lcp[rank[i]]=k;
- }
- return lcp;
- }
- #if defined(WITH_FUNCTION)
- void printVector(std::vector<int> const &input)
- {
- #if defined(OPTION_1)
- for (int i = 0; i < input.size(); i++) {
- std::cout << input.at(i) << ' ';
- }
- #elif defined(OPTION_2)
- for (auto const &i: input) {
- std::cout << i << " ";
- }
- #elif defined(OPTION_3)
- std::copy(input.begin(),
- input.end(),
- std::ostream_iterator<int>(std::cout, " "));
- #endif
- }
- #else
- std::ostream &operator<<(std::ostream &os, const std::vector<int> &input)
- {
- for (auto const &i: input) {
- os << i << " ";
- }
- return os;
- }
- #endif
- main()
- {
- std::string myInput;
- cout << "enter the string : " << endl;
- getline(cin,myInput);
- vector<int> vec(myInput.size(),0);
- auto lcp = kasai(myInput, vec);
- #if defined(WITH_FUNCTION)
- printVector(lcp);
- #else
- cout << " the vector now prints normally " << lcp << endl;
- #endif
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement