Advertisement
sacr1ficerq

D

Sep 14th, 2022
45
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. vector<int> z_f(string s){
  9.     int n = s.size();
  10.     int R = 0;
  11.     int L = 0;
  12.     vector<int> Z(n, 0);
  13.  
  14.     for (int i = 1; i < n; ++i) {
  15.         if (i > R) {
  16.             // calculating new substring
  17.             L = R = i;
  18.             while (s[R] == s[R - L] && R < n) {
  19.                 R++;
  20.             }
  21.             R--;
  22.             Z[i] = R - L + 1;
  23.             // calculated
  24.         } else {
  25.             // we are inside substring
  26.             if (Z[i - L] < R - i + 1) {
  27.                 Z[i] = Z[i - L];
  28.             } else {
  29.                 // we might be inside our own substring like in last character of "abcabca" (its not 4)
  30.                 L = i;
  31.                 while (s[R] == s[R - L] && R < n) {
  32.                     R++;
  33.                 }
  34.                 R--;
  35.                 Z[i] = R - L+1;
  36.             }
  37.         }
  38.     }
  39.     return Z;
  40. }
  41.  
  42. void display(const vector<int> &v){
  43.     for (const auto& e : v){
  44.         cout << e%10 << " ";
  45.     }
  46.     cout << endl;
  47. }
  48.  
  49. int main (){
  50.     string pattern;
  51.     string input;
  52.  
  53.     cin >> pattern >> input;
  54.  
  55.     string s1 = pattern+"@"+input;
  56.     string s2 = input+"@"+pattern;
  57.     reverse(s2.begin(), s2.end());
  58.  
  59.     vector<int> z_v = z_f(s1);
  60.     z_v = {z_v.begin()+pattern.size()+1, z_v.end()};
  61.  
  62.  
  63.  
  64.     vector<int> z_r_v = z_f(s2);
  65.     z_r_v = {z_r_v.begin() + pattern.size() + 1, z_r_v.end()};
  66.     reverse(z_r_v.begin(), z_r_v.end());
  67.  
  68.  
  69.     vector<int> occurrences;
  70.  
  71.     int l = 0, r = pattern.size()-1;
  72.  
  73.     while (r<input.size()){
  74.         if (z_v[l] + z_r_v[r] >= pattern.size()-1){
  75.             occurrences.push_back(l+1);
  76.         }
  77.  
  78.         ++l;
  79.         ++r;
  80.     }
  81.     cout << occurrences.size() << endl;
  82.  
  83.     for (const auto& e : occurrences){
  84.         cout << e << " ";
  85.     }
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement