cf D. Sereja ans Anagrams

http://codeforces.com/contest/368/problem/D
 1 #include <cstdio>
 2 #include <cstring>
 3 #include <map>
 4 #include <vector>
 5 #include <algorithm>
 6 #define maxn 300000
 7 #define LL long long
 8 using namespace std;
 9 
10 int n,m,p;
11 LL a[maxn],b[maxn];
12 vector<int>g;
13 
14 int main()
15 {
16     while(scanf("%d%d%d",&n,&m,&p)!=EOF)
17     {
18         for(int i=0; i<n; i++)
19         {
20             scanf("%lld",&a[i]);
21         }
22         for(int i=0; i<m; i++)
23         {
24             scanf("%lld",&b[i]);
25         }
26         for(int i=0; i<p&&i+(LL)(m-1)*p<n; i++)
27         {
28             map<int,int>q;
29             for(int j=0; j<m; j++)
30             {
31                 q[b[j]]++;
32             }
33             int c=i;
34             for(int j=0; j<m; j++)
35             {
36                 q[a[c]]--;
37                 if(q[a[c]]==0)
38                 {
39                     q.erase(a[c]);
40                 }
41                 c+=p;
42             }
43             for(int j=i; ; j+=p,c+=p)
44             {
45                 if(!q.size()) g.push_back(j+1);
46                 if(c>=n) break;
47                 if(--q[a[c]]==0) q.erase(a[c]);
48                 if(++q[a[j]]==0) q.erase(a[j]);
49             }
50         }
51         sort(g.begin(),g.end());
52         printf("%d
",g.size());
53         for(int i=0; i<(int)g.size(); i++)
54         {
55             printf("%d ",g[i]);
56         }
57         printf("
");
58     }
59     return 0;
60 }
View Code