mayoko’s diary

プロコンとかいろいろ。

Codeforces Round #215 (Div. 1) B. Sereja ans Anagrams

解法

配列 a の s 〜 s+p*(m-1) にある, p 個おきの 配列 b の要素数を数えます。

この要素数が b の要素数と一致していれば嬉しいですが, これを高速に数えたいです。

これは, 蟻本の p137, p138 に書いてある問題と似ています。
cnt[i] = (配列 b の i 番目に小さい要素が考えている区間に含まれている数), target[i] = (配列 b の i 番目に小さい要素が含まれている数(配列 b の考える区間は変わらないので, これは一定)), num = (cnt[i] >= target[i] を満たす i の数) として, 配列 a の m 個の要素で num の数が配列 b の異なる要素の数に一致すれば, s からの m 要素は b と一致させることが出来ます。

const int MAXN = 200200;
int a[MAXN], b[MAXN];

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        scanf("%d", a+i);
    }
    for (int i = 0; i < m; i++) {
        scanf("%d", b+i);
        mp[b[i]] = 0;
    }
    vector<int> ans;
    int k = 0;
    for (auto& p : mp) p.second = k++;
    vector<int> target(k);
    for (int i = 0; i < m; i++) target[mp[b[i]]]++;
    for (int i = 0; i < p; i++) {
        if (i+(ll)(m-1)*p >= n) continue;
        int num = 0;
        vector<int> cnt(k);
        for (int j = 0; j < m; j++) {
            if (mp.find(a[i+j*p]) != mp.end()) {
                int index = mp[a[i+j*p]];
                if (++cnt[index] == target[index]) num++;
            }
        }
        if (num == k) ans.push_back(i);
        for (int j = m; i+j*p < n; j++) {
            if (mp.find(a[i+(j-m)*p]) != mp.end()) {
                int index = mp[a[i+(j-m)*p]];
                if (cnt[index]-- == target[index]) num--;
            }
            if (mp.find(a[i+j*p]) != mp.end()) {
                int index = mp[a[i+j*p]];
                if (++cnt[index] == target[index]) num++;
            }
            if (num == k) ans.push_back(i+(j-m+1)*p);
        }
    }
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (int el : ans) printf("%d ", el+1);
    printf("\n");
    return 0;
}