Codeforces 367B - Sereja ans Anagrams(map)

B. Sereja ans Anagrams time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Sereja has two sequences a and b and number p. Sequence a consists of n integers a1, a2, …, an. Similarly, sequence b consists of m integers b1, b2, …, bm. As usual, Sereja studies the sequences he has. Today he wants to find the number of positions q (q + (m - 1)·p ≤ n; q ≥ 1), such that sequence b can be obtained from sequence aq, aq + p, aq + 2p, …, aq + (m - 1)p by rearranging elements.
Sereja needs to rush to the gym, so he asked to find all the described positions of q.
Input The first line contains three integers n, m and p (1 ≤ n, m ≤ 2·105, 1 ≤ p ≤ 2·105). The next line contains n integers a1, a2, …, an (1 ≤ ai ≤ 109). The next line contains m integers b1, b2, …, bm (1 ≤ bi ≤ 109).
Output In the first line print the number of valid qs. In the second line, print the valid values in the increasing order.
Examples input 5 3 1 1 2 3 2 1 1 2 3 output 2 1 3 input 6 3 2 1 3 2 2 3 1 1 2 3 output 2 1 2
제목: 문자열 a와 b, 그리고 정수 p. a의 어느 위치에서부터 p의 길이마다 문자를 하나씩 가져오라고 합니다. 이렇게 하면 몇 조를 꺼낼 수 있는지 물어보면 꺼낸 문자열이 b와 같을 수 있습니다(순서가 다를 수 있습니다).
문제풀이 사고방식: 각 위치를 매개하고 꺼낸 것을 queue에 넣고 길이가 b와 같으면 한 번 비교한 다음에 pop(), 하나를 내려놓으면 복잡도가 O(n)임을 보증한다.비교할 때 맵을 사용할 수 있습니다. 무질서하기 때문입니다.
AC 코드:

#include 
using namespace std;
const int maxn = 2e5+5;
map <int, int> mp;
map <int, int> b;
bool vis[maxn];
int a[maxn];
int n, m, p;
int res = 0;


void fun(int s)
{
    queue <int> Q;
    mp.clear();
    for(int i = s; i <= n; i += p){
        Q.push(i);
        mp[a[i]]++;
        if(Q.size() == m){
            if(mp == b){
                vis[Q.front()] = 1;
                res++;
            }
            int tmp = Q.front();
            Q.pop();
            mp[a[tmp]]--;
            if(!mp[a[tmp]])
                mp.erase(a[tmp]);
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin >> n >> m >> p;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= m; i++){
        int tmp;
        cin >> tmp;
        b[tmp]++;
    }
    for(int i = 1; i <= p; i++)
        fun(i);
    cout << res << endl;
    for(int i = 1; i <= n; i++)
        if(vis[i])
            cout << i << " ";
    return 0;
}