Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- #include <map>
- #include <cassert>
- using namespace std;
- struct Node{
- Node() = default;
- void add_neighbour(char c, int n){
- transitions_.insert({c, n});
- }
- int get_neighbour(char c){
- assert(transitions_.contains(c));
- return transitions_[c];
- }
- private:
- map<char, int> transitions_;
- };
- vector<int> prefix_f(string s){
- auto n = s.size();
- vector<int> pf(n, 0);
- for (int i = 1; i < n; ++i){
- auto j = pf[i-1];
- while (s[j] != s[i]){
- if (j == 0){
- j = -1;
- break;
- }
- j = pf[j-1];
- }
- pf[i] = j+1;
- }
- return pf;
- }
- class KMP{
- public:
- explicit KMP(string& s, vector<char>& alphabet){
- for (int i = 0; i < s.size()+1; ++i){
- Node* new_node = new Node();
- spanning_tree.push_back(new_node);
- }
- if (s.empty()){
- return;
- }
- auto m = s.size();
- prefix_v = prefix_f(s);
- for (int q = 0; q < m+1; ++q){
- for (char c : alphabet){
- if (q > 0 && c != s[q]){
- auto address = get_transition(prefix_v[q-1], c);
- add_transition(q, c, address);
- }
- else {
- add_transition(q, c, q + (c == s[q]));
- }
- }
- }
- }
- vector<Node*> spanning_tree;
- vector<int> prefix_v;
- void add_transition(int n, char a, int direction){
- assert(n<=spanning_tree.size());
- spanning_tree[n]->add_neighbour(a, direction);
- }
- int get_transition(int n, char c){
- return spanning_tree[n]->get_neighbour(c);
- }
- };
- int main(){
- int o;
- cin >> o;
- int alphabet_size;
- cin >> alphabet_size;
- int interruptions;
- cin >> interruptions;
- string s;
- cin >> s;
- vector<char> alphabet;
- char last = 'a';
- for (int i = 0; i < alphabet_size; ++i){
- alphabet.push_back(last);
- ++last;
- }
- KMP kmp = KMP(s, alphabet);
- int64_t result = s.size();
- // TODO: length of the rest of string with max from alphabet interuption
- // (string length before interruption) + (string length between interuptions)*interruptions + (length of string after interruption)
- int last_change = 0;
- for (int i = 1; i < s.size(); ++i){ //iterating over fav word
- // finding max (string length between interuptions)
- int64_t between = 0;
- int64_t before = 0;
- int64_t after = 0;
- for (auto c : alphabet){
- auto r = kmp.spanning_tree[i]->get_neighbour(c);
- between = i - r;
- before = r;
- after = s.size() - i;
- if (before + between*(interruptions+1) + after > result){
- result = before + between*(interruptions+1) + after;
- last_change = i;
- }
- }
- }
- cout << result;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement