Advertisement
Guest User

Untitled

a guest
Dec 12th, 2019
109
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.96 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include<string>
  4.  
  5. namespace StringProcessing
  6. {
  7.     std::string getStrByPrefix(const std::vector<size_t> & prefix_function)
  8.     {
  9.         if (!prefix_function.size())
  10.         {
  11.             return "";
  12.         }
  13.         std::string str = "a";
  14.  
  15.         for (size_t i = 1; i < prefix_function.size(); i++)
  16.         {
  17.             if (prefix_function[i] != 0)
  18.             {
  19.                 str += str[prefix_function[i] - 1];
  20.             }
  21.             else
  22.             {
  23.                 std::vector<bool> used(26, false);
  24.                 size_t k = prefix_function[i - 1];
  25.                 while (k > 0)
  26.                 {
  27.                     used[str[k] - 'a'] = true;
  28.                     k = prefix_function[k - 1];
  29.                 }
  30.                 char curr_symb = 'b';
  31.                 while (used[curr_symb - 'a'])
  32.                 {
  33.                     curr_symb++;
  34.                 };
  35.                 str += curr_symb;
  36.             }
  37.         }
  38.         return str;
  39.     }
  40. }
  41.  
  42.  
  43. int main()
  44. {
  45.     size_t n;
  46.     std::cin >> n;
  47.     std::vector<size_t> prefix_function(n);
  48.     for (size_t i = 0; i < n; i++)
  49.     {
  50.         std::cin >> prefix_function[i];
  51.     }
  52.     std::cout << StringProcessing::getStrByPrefix(prefix_function);
  53.    
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement