fork download
copy 
  1. ///            ,-----v-----.
  2. ///           /             \
  3. ///          /   _       _   \
  4. ///         |   / \     / \   |
  5. ///         |  |   |   |   |  |
  6. ///         |  |   |   |   |  |
  7. ///         |   \ /     \ /   |
  8. ///         |    '       '    |
  9. ///        /                   \
  10. ///       |   ( O )     ( O )   |
  11. ///       |          ♥          |
  12. ///       |         \_/         |
  13. ///        \                   /
  14. ///         '--.___________.--'
  15. ///            /           \
  16. ///           /             \
  17. ///          /  /|  (✿)  |\  \
  18. ///         /  / |       | \  \
  19. ///        /  /  |_______|  \  \
  20. ///       |__/    |  |  |    \__|
  21. ///               |  |  |
  22. ///                -   -
  23.  
  24. #include <bits/stdc++.h>
  25. using namespace std;
  26.  
  27. #define Task "Test"
  28. #define int long long
  29. #define el '\n'
  30. #define cnt_bit_1 __builtin_popcountll
  31. #define float double
  32. #define IO freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout);
  33. #define pii pair<int,int>
  34. #define fi first
  35. #define se second
  36. #define pb push_back
  37.  
  38. const int N=2e5+5;
  39. const int INF=1e18;
  40. const int MOD=1e9+7;
  41.  
  42. int n , m;
  43.  
  44. vector<int> prefix_function(vector<int> s)
  45. {
  46.     int n = s.size();
  47.     vector<int> pi(n , 0);
  48.  
  49.     for(int i = 1; i < n; i++)
  50.     {
  51.         int j = pi[i - 1];
  52.         while (j > 0 && s[i] != s[j]) j = pi[j - 1];
  53.         if(s[i] == s[j]) j++;
  54.         pi[i] = j;
  55.     }
  56.     return pi;
  57. }
  58.  
  59. signed main()
  60. {
  61.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  62.     //IO
  63.  
  64.     cin >> n >> m;
  65.  
  66.     vector<int> t(n + 1) , p(m + 1);
  67.     for(int i = 1; i <= n; i++) cin >> t[i];
  68.     for(int i = 1; i <= m; i++) cin >> p[i];
  69.  
  70.     if(m == 1)
  71.     {
  72.         cout << n << el;
  73.         for(int i = 1; i <= n; i++) cout << i << ' ';
  74.         return 0;
  75.     }
  76.  
  77.     vector<int> a , b;
  78.     for(int i = 1; i < n; i++) a.pb(t[i + 1] - t[i]);
  79.     for(int i = 1; i < m; i++) b.pb(p[i + 1] - p[i]);
  80.  
  81.     vector<int> pi = prefix_function(b);
  82.     vector<int> ans;
  83.  
  84.     int j = 0;
  85.     for(int i = 0; i < a.size(); i++)
  86.     {
  87.         while(j > 0 && a[i] != b[j]) j = pi[j - 1];
  88.         if(a[i] == b[j]) j++;
  89.         if(j == b.size())
  90.         {
  91.             ans.pb(i - b.size() + 2);
  92.             j = pi[j - 1];
  93.         }
  94.     }
  95.  
  96.     cout << ans.size() << el;
  97.     for(int i = 0; i < ans.size(); i++) cout << ans[i] << ' ';
  98.  
  99.     return 0;
  100. }
  101.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kvOAIn
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!