Untitled
unknown
plain_text
a month ago
3.2 kB
3
Indexable
#include <iostream> #include <vector> #include <string> std::vector<int> prefix_function(const std::string& str) { int n = str.length(); if(n == 0) return std::vector<int> (0); std::vector<int> prefix_arr(n); int j; for (int i = 1; i < n; ++i) { j = prefix_arr[i - 1]; while (j > 0 && str[i] != str[j]) j = prefix_arr[j - 1]; if (str[i] == str[j]) j++; prefix_arr[i] = j; } return prefix_arr; } std::vector<int> kmp(const std::string& patt, const std::string& temp, bool stop_at_first) { std::vector<int> answer; int patt_len = patt.size(); int temp_len = temp.size(); if(patt_len == 0 || temp_len == 0) { answer.push_back(-1); return answer; } std::vector<int> p = prefix_function(patt + "#"); int j = 0; for(int i = 0; i < temp_len; ++i) { while(j > 0 && patt[j] != temp[i]) j = p[j-1]; if(patt[j] == temp[i]) j++; if(j == patt_len) { answer.push_back(i - patt_len + 1); if(stop_at_first) break; } } if(!answer.size()) answer.push_back(-1); return answer; } int check_cycle(const std::string& patt, const std::string& temp) { int patt_len = patt.size(); int temp_len = temp.size(); if(patt_len == 0 || temp_len == 0) return -1; if(patt_len != temp_len) return -1; std::vector<int> res = kmp(temp, patt + patt, true); return res[0]; } bool read_strings(std::string& patt, std::string& temp, std::istream& in) { in >> patt; in >> temp; if(patt.size() == 0 || temp.size() == 0) return false; return true; } void print_vector(const std::vector<int>& vec) { for(int i = 0; i < vec.size(); ++i) { if(i == vec.size() - 1) { std::cout << vec[i] << "\n"; } else { std::cout << vec[i] << ","; } } } int main(int argc, char** argv) { int task = 1; for(int i = 0; i < argc; ++i) { if(std::string(argv[i]) == "-kmp") { task = 1; break; } else if(std::string(argv[i]) == "-cycle") { task = 2; break; } else if(std::string(argv[i]) == "-h" || std::string(argv[i]) == "--help") { task = 0; break; } } if(task == -1) { std::cout << "You have to specialize the task: either choose KMP or Cycle Check.\nTo get more info use key -h or --help.\n"; return 0; } else if(task == 0) { std::cout << "Use -kmp to start Knuth–Morris–Pratt Algorithm\n"; std::cout << "Use -cycle to check if a string is a cycle shift of another one\n"; return 0; } std::string pattern, temp; if(!read_strings(pattern, temp, std::cin)) { std::cout << "You've entered empty string\n"; return 0; } if(task == 1) { std::vector<int> res = kmp(pattern, temp, false); print_vector(res); return 0; } else { std::cout << check_cycle(pattern, temp) << '\n'; return 0; } return 0; }
Editor is loading...
Leave a Comment