Advertisement
sacr1ficerq

E

Sep 14th, 2022
35
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.10 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <map>
  5. #include <cassert>
  6.  
  7. using namespace std;
  8.  
  9.  
  10. struct Node{
  11.  
  12.     Node() = default;
  13.  
  14.     void add_neighbour(char c, int n){
  15.         transitions_.insert({c, n});
  16.     }
  17.  
  18.     int get_neighbour(char c){
  19.         assert(transitions_.contains(c));
  20.         return transitions_[c];
  21.     }
  22.  
  23. private:
  24.     map<char, int> transitions_;
  25.  
  26.  
  27. };
  28.  
  29. vector<int> prefix_f(string s){
  30.     auto n = s.size();
  31.  
  32.     vector<int> pf(n, 0);
  33.  
  34.     for (int i = 1; i < n; ++i){
  35.         auto j = pf[i-1];
  36.         while (s[j] != s[i]){
  37.             if (j == 0){
  38.                 j = -1;
  39.                 break;
  40.             }
  41.             j = pf[j-1];
  42.         }
  43.         pf[i] = j+1;
  44.     }
  45.  
  46.     return pf;
  47. }
  48.  
  49. class KMP{
  50. public:
  51.     explicit KMP(string& s, vector<char>& alphabet){
  52.         for (int i = 0; i < s.size()+1; ++i){
  53.             Node* new_node = new Node();
  54.             spanning_tree.push_back(new_node);
  55.         }
  56.         if (s.empty()){
  57.             return;
  58.         }
  59.         auto m = s.size();
  60.  
  61.         prefix_v = prefix_f(s);
  62.  
  63.         for (int q = 0; q < m+1; ++q){
  64.             for (char c : alphabet){
  65.                 if (q > 0 && c != s[q]){
  66.                     auto address = get_transition(prefix_v[q-1], c);
  67.                     add_transition(q, c, address);
  68.                 }
  69.                 else {
  70.                     add_transition(q, c, q + (c == s[q]));
  71.                 }
  72.             }
  73.         }
  74.  
  75.     }
  76.  
  77.     vector<Node*> spanning_tree;
  78.     vector<int> prefix_v;
  79.  
  80.  
  81.     void add_transition(int n, char a, int direction){
  82.         assert(n<=spanning_tree.size());
  83.  
  84.         spanning_tree[n]->add_neighbour(a, direction);
  85.     }
  86.  
  87.     int get_transition(int n, char c){
  88.         return spanning_tree[n]->get_neighbour(c);
  89.     }
  90. };
  91.  
  92.  
  93. int main(){
  94.     int o;
  95.     cin >> o;
  96.  
  97.     int alphabet_size;
  98.     cin >> alphabet_size;
  99.  
  100.     int interruptions;
  101.     cin >> interruptions;
  102.  
  103.     string s;
  104.     cin >> s;
  105.  
  106.     vector<char> alphabet;
  107.  
  108.     char last = 'a';
  109.  
  110.     for (int i = 0; i < alphabet_size; ++i){
  111.         alphabet.push_back(last);
  112.         ++last;
  113.     }
  114.  
  115.     KMP kmp = KMP(s, alphabet);
  116.  
  117.     int64_t result = s.size();
  118.  
  119.     // TODO: length of the rest of string with max from alphabet interuption
  120.     // (string length before interruption) + (string length between interuptions)*interruptions + (length of string after interruption)
  121.  
  122.     int last_change = 0;
  123.  
  124.     for (int i = 1; i < s.size(); ++i){ //iterating over fav word
  125.         // finding max (string length between interuptions)
  126.         int64_t between = 0;
  127.         int64_t before = 0;
  128.         int64_t after = 0;
  129.  
  130.         for (auto c : alphabet){
  131.             auto r = kmp.spanning_tree[i]->get_neighbour(c);
  132.             between = i - r;
  133.             before = r;
  134.             after = s.size() - i;
  135.  
  136.             if (before + between*(interruptions+1) + after > result){
  137.                 result = before + between*(interruptions+1) + after;
  138.                 last_change = i;
  139.             }
  140.         }
  141.     }
  142.  
  143.     cout << result;
  144.  
  145.     return 0;
  146. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement