#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define endl '\n'
typedef unsigned int uint;
typedef unsigned int ll;
typedef long double ld;
typedef unsigned long long ull;
using namespace std;
const ll maxn = 1e6;
const ll modd = 65537
;
const ll modd2 = 65539;
const ll p1 = 10007
;
const ll p2 = 10009;
ll P1[maxn + 1], P2[maxn + 1];
ll M;
ll f_H1(vector<ll> &A)
{
ll res = 0;
for (int i = 0; i < A.size(); i++)
{
res += (A[i]%modd * P1[i]) % modd;
res %= modd;
}
return res;
}
ll f_H2(vector<ll> &A)
{
ll res = 0;
for (int i = 0; i < A.size(); i++)
{
res += (A[i]%modd2 * P2[i]) % modd2;
res %= modd2;
}
return res;
}
ll h1[(1LL<<19)*3];
ll h2[(1LL<<19)*3];
ll sz[(1LL<<19)*3];
ll ans[(1LL<<19)*3];
map<ll, ll> mp;
void update(ll need, ll val)
{
ll cur = M + need - 1;
h1[cur] =(val%modd);
h2[cur] =(val%modd2);
sz[cur] = (val != 0);
cur/=2;
while(cur){
h1[cur] = (h1[cur+cur] + (h1[cur+cur+1] * P1[ sz[cur+cur] ])%modd)%modd;
h2[cur] = (h2[cur+cur] + (h2[cur+cur+1] * P2[ sz[cur+cur] ])%modd2)%modd2;
sz[cur]=sz[cur+1+cur]+sz[cur+cur];
cur/=2;
}
}
signed main()
{
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
cout.tie(NULL);
ll n, m;
cin >> n >> m;
vector<ll>a(n+1) , b(m+1);
P1[0] = P2[0] = 1;
ll add1 = 1, add2 = 1;
for (int i = 1; i <= 1 + n; i++)
{
P1[i] = (P1[i - 1] * p1) % modd;
P2[i] = (P2[i - 1] * p2) % modd2;
if (i < n)
{
add1 = (add1 + P1[i]) % modd;
add2 = (add2 + P2[i]) % modd2;
}
}
M =m;
if( (m & (m-1))){
M = (1 << ll(log2(m)+1) );
}
for (int i = 0; i < n; i++)
cin >> a[i];
for (int j = 0; j < m; j++)
{
cin >> b[j];
mp[b[j]];
}
int ind = 0;
for (auto &g : mp)
{
ind++;
g.second = ind;
}
ll Hx1 = f_H1(a);
ll Hx2 = f_H2(a);
ll kol = 0;
ll __sz = 0;
for (int j = 0; j < m; j++)
{
update(mp[b[j]], j + 1);
if (sz[1] > n)
{
update(mp[b[j - n]], 0);
Hx1 = (Hx1 + add1) % modd;
Hx2 = (Hx2 + add2) % modd2;
}
if (sz[1] < n)
continue;
if (h1[1] == Hx1 && h2[1] == Hx2)
{
__sz++;
ans[__sz-1] = j-n+2;
}
}
cout<<__sz<<endl;
for(int i = 0;i < __sz;i++){
cout<<ans[i]<<' ';
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |